Ugly Number

EASY

Description

An ugly number is a positive integer which does not have a prime factor other than 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

Example 1:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: n = 1
Output: true
Explanation: 1 has no prime factors.

Example 3:

Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

Constraints:

-2³¹ <= n <= 2³¹ - 1

Approaches

Checkout 2 different approaches to solve Ugly Number. Click on different approaches to view the approach and algorithm in detail.

Brute Force Prime Factorization

Check if the number has any prime factors other than 2, 3, and 5 by trying to divide by all numbers up to sqrt(n).

Algorithm

If n ≤ 0, return false as ugly numbers are positive
For each number i from 2 to sqrt(n):
- While n is divisible by i:
  - If i is not 2, 3, or 5, return false
  - Divide n by i
If remaining n > 5, return false
Return true

This approach involves checking all possible prime factors of the number n by iterating through numbers from 2 to sqrt(n). For each number, we keep dividing n by it as long as possible. If we encounter any prime factor other than 2, 3, or 5, we return false.

public boolean isUgly(int n) {
    if (n <= 0) return false;
    
    // Try dividing by numbers up to sqrt(n)
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            // If we find a prime factor other than 2, 3, or 5
            if (i != 2 && i != 3 && i != 5) {
                return false;
            }
            n /= i;
        }
    }
    
    // Check if remaining number is greater than 5
    if (n > 5) return false;
    
    return true;
}

Complexity Analysis

Time Complexity: O(sqrt(n)) - We need to check all numbers up to sqrt(n)Space Complexity: O(1) - Only uses a constant amount of extra space

Pros and Cons

Pros:

Simple to understand and implement
Works for all input cases

Cons:

Not the most efficient solution
Checks unnecessary numbers that aren't prime factors

Code Solutions

Checking out 4 solutions in different languages for Ugly Number. Click on different languages to view the code.

class Solution {
public
  boolean isUgly(int n) {
    if (n < 1)
      return false;
    while (n % 2 == 0) {
      n /= 2;
    }
    while (n % 3 == 0) {
      n /= 3;
    }
    while (n % 5 == 0) {
      n /= 5;
    }
    return n == 1;
  }
}

Video Solution

Watch the video walkthrough for Ugly Number

Patterns:

Math

Companies:

J.P. Morgan |