Problem Description

An ugly number is defined as a positive integer whose only prime factors are 2, 3, and 5. In other words, when you break down the number into its prime factorization, it should only contain the primes 2, 3, and/or 5 (or no prime factors at all, which would be the number 1).

Given an integer n, you need to determine whether n is an ugly number or not. Return true if it is an ugly number, and false otherwise.

For example:

• 1 is an ugly number (it has no prime factors)
• 6 is an ugly number (6 = 2 × 3)
• 8 is an ugly number (8 = 2³)
• 14 is not an ugly number (14 = 2 × 7, and 7 is a prime factor other than 2, 3, or 5)

The solution works by repeatedly dividing n by 2, 3, and 5 as long as possible. If after removing all factors of 2, 3, and 5, we're left with 1, then the original number was an ugly number. If we're left with any other number, it means there are other prime factors present, so it's not an ugly number.

Note that negative numbers and zero are not considered ugly numbers by definition, since ugly numbers must be positive integers.

Intuition

The key insight is that if a number is ugly, it can be expressed as 2^a × 3^b × 5^c where a, b, and c are non-negative integers. This means we should be able to completely reduce the number to 1 by repeatedly dividing it by 2, 3, and 5.

Think of it like peeling away layers: if we keep removing all factors of 2, 3, and 5 from the number, and there's nothing left (we get 1), then the number was made up entirely of these prime factors. If there's something else remaining, it means there are other prime factors involved.

For instance, take the number 30:

• 30 ÷ 2 = 15
• 15 ÷ 3 = 5
• 5 ÷ 5 = 1

We successfully reduced it to 1, so 30 is ugly.

Now consider 14:

• 14 ÷ 2 = 7
• 7 is not divisible by 2, 3, or 5

We're stuck with 7, which is a prime number other than 2, 3, or 5. So 14 is not ugly.

The algorithm naturally follows: for each of the allowed prime factors (2, 3, 5), divide the number by that factor as many times as possible. After exhausting all divisions by 2, 3, and 5, check if we're left with 1. If yes, the number is ugly; if not, it contains other prime factors and is not ugly.

Solution Approach

The implementation follows a straightforward iterative approach:

1. Handle Edge Cases: First, we check if n < 1. Since ugly numbers must be positive integers, any number less than 1 is immediately not ugly, so we return False.

2. Iterative Division: We iterate through each of the allowed prime factors [2, 3, 5]. For each prime factor x:

   • We use a while loop to repeatedly divide n by x as long as n is divisible by x (i.e., n % x == 0)
   • Each time we find that n is divisible by x, we update n by performing integer division: n //= x
   • This continues until n is no longer divisible by x, effectively removing all factors of x from n

3. Final Check: After processing all three prime factors, we check if n == 1:

   • If n equals 1, it means we successfully factored out all prime components using only 2, 3, and 5, so the number is ugly
   • If n is not 1, there are other prime factors remaining, so the number is not ugly

The algorithm has a time complexity of O(log n) because in the worst case, we might need to divide n by 2 repeatedly until we reach 1 (for example, when n is a power of 2). The space complexity is O(1) as we only use a constant amount of extra space.

Example walkthrough with n = 12:

• Initially n = 12
• Divide by 2: 12 ÷ 2 = 6, then 6 ÷ 2 = 3, then 3 is not divisible by 2
• Divide by 3: 3 ÷ 3 = 1, then 1 is not divisible by 3
• Divide by 5: 1 is not divisible by 5
• Final value: n = 1, so return True

Example Walkthrough

Let's walk through the solution with n = 30:

Initial State: n = 30

Step 1: Remove all factors of 2

• Check: Is 30 divisible by 2? Yes (30 % 2 = 0)
• Divide: 30 ÷ 2 = 15
• Check: Is 15 divisible by 2? No (15 % 2 = 1)
• Current value: n = 15

Step 2: Remove all factors of 3

• Check: Is 15 divisible by 3? Yes (15 % 3 = 0)
• Divide: 15 ÷ 3 = 5
• Check: Is 5 divisible by 3? No (5 % 3 = 2)
• Current value: n = 5

Step 3: Remove all factors of 5

• Check: Is 5 divisible by 5? Yes (5 % 5 = 0)
• Divide: 5 ÷ 5 = 1
• Check: Is 1 divisible by 5? No (1 % 5 = 1)
• Current value: n = 1

Final Check: Is n == 1? Yes, so return True. The number 30 is ugly.

Let's contrast this with a non-ugly number, n = 14:

Initial State: n = 14

Step 1: Remove all factors of 2

• Check: Is 14 divisible by 2? Yes (14 % 2 = 0)
• Divide: 14 ÷ 2 = 7
• Check: Is 7 divisible by 2? No (7 % 2 = 1)
• Current value: n = 7

Step 2: Remove all factors of 3

• Check: Is 7 divisible by 3? No (7 % 3 = 1)
• Current value: n = 7

Step 3: Remove all factors of 5

• Check: Is 7 divisible by 5? No (7 % 5 = 2)
• Current value: n = 7

Final Check: Is n == 1? No, n = 7. Since 7 is a prime factor other than 2, 3, or 5, return False. The number 14 is not ugly.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The algorithm repeatedly divides n by 2, 3, and 5 while these divisions are possible. In the worst case:

• Dividing by 2 removes all powers of 2, which takes at most log₂(n) iterations
• Dividing by 3 removes all powers of 3, which takes at most log₃(n) iterations
• Dividing by 5 removes all powers of 5, which takes at most log₅(n) iterations

The total number of iterations is bounded by log₂(n) + log₃(n) + log₅(n), which is O(log n) since all logarithms differ only by a constant factor.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. It modifies the input value n in-place and uses a fixed-size list [2, 3, 5] for iteration. No additional data structures that grow with input size are used.

Common Pitfalls

1. Not Handling Non-Positive Numbers Correctly

A frequent mistake is forgetting to check if the input is positive, or incorrectly handling the edge case of n = 0 or negative numbers.

Incorrect Implementation:

def isUgly(self, n: int) -> bool:
    # Missing check for non-positive numbers
    for factor in [2, 3, 5]:
        while n % factor == 0:  # This will cause ZeroDivisionError when n = 0
            n //= factor
    return n == 1

Why It's Wrong:

• When n = 0, the modulo operation 0 % factor returns 0, causing an infinite loop
• Negative numbers would be processed incorrectly since they could become -1 after division

Correct Approach:

def isUgly(self, n: int) -> bool:
    if n < 1:  # Properly handle non-positive numbers
        return False
    # ... rest of the code

2. Using Recursion Without Proper Base Cases

Some might attempt a recursive solution but forget proper termination conditions.

Problematic Recursive Implementation:

def isUgly(self, n: int) -> bool:
    if n == 1:
        return True
    # Missing check for n < 1
    for factor in [2, 3, 5]:
        if n % factor == 0:
            return self.isUgly(n // factor)
    return False

Why It's Wrong:

• Doesn't handle negative numbers or zero, potentially causing stack overflow
• For n = 0, it will infinitely recurse since 0 // factor = 0

Better Recursive Approach:

def isUgly(self, n: int) -> bool:
    if n < 1:
        return False
    if n == 1:
        return True
    for factor in [2, 3, 5]:
        if n % factor == 0:
            return self.isUgly(n // factor)
    return False

3. Inefficient Order of Prime Factors

While not incorrect, checking factors in a suboptimal order can lead to more iterations.

Less Efficient:

prime_factors = [5, 3, 2]  # Checking larger factors first

More Efficient:

prime_factors = [2, 3, 5]  # Checking smaller factors first

Why It Matters: Numbers are more likely to have smaller prime factors. For example, checking and removing all factors of 2 first (which appears most frequently) reduces the number more quickly, making subsequent divisions faster.

4. Integer Overflow Concerns in Other Languages

While Python handles arbitrary precision integers automatically, in languages like Java or C++, you might encounter overflow issues.

Potential Issue in Other Languages:

• Very large numbers might cause overflow during intermediate calculations
• Need to be careful with the data type used (int vs long in Java)

Python Advantage: Python's automatic handling of big integers means this isn't a concern, but it's worth noting when translating the solution to other languages.