Code Implementation

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

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

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        int[] primes = {2, 3, 5};
        for (int p : primes) {
            while (n % p == 0) {
                n /= p;
            }
        }
        return n == 1;
    }
}
      

var isUgly = function(n) {
    if (n <= 0) return false;
    const primes = [2, 3, 5];
    for (let p of primes) {
        while (n % p === 0) {
            n /= p;
        }
    }
    return n === 1;
};
      

Problem Description

The Ugly Number problem asks you to determine whether a given integer n is an "ugly number." A number is considered ugly if its only prime factors are 2, 3, or 5. In other words, after repeatedly dividing n by 2, 3, and 5 (as many times as possible), you should end up with 1 if n is ugly.

• If n is less than or equal to 0, it is not considered ugly.
• Only positive integers are considered.
• There is no need to reuse elements or find combinations; just check the factorization of n.

Thought Process

At first glance, you might think you need to check all possible prime factors of n. However, the problem specifically restricts ugly numbers to those whose only prime factors are 2, 3, or 5. This means that any other prime factor (like 7 or 11) immediately disqualifies n from being ugly.

The brute-force approach would be to factorize n and check if any prime factors other than 2, 3, or 5 exist. But we can optimize by simply dividing n by 2, then by 3, then by 5, as many times as possible. If after all these divisions we're left with 1, then n had no other prime factors.

This approach is both simple and efficient, as we only care about three divisors and don't need to generate or check all primes.

Solution Approach

Here’s a step-by-step breakdown of the algorithm:

1. Check for Non-Positive Numbers: If n is less than or equal to zero, immediately return False. Ugly numbers must be positive.
2. Repeated Division: For each prime factor (2, 3, 5):
   • While n is divisible by the current prime, divide n by that prime.
   • Repeat for all three primes.
3. Final Check: After all divisions, if n equals 1, then it is ugly (since it only had 2, 3, and 5 as factors). Otherwise, it is not ugly.

We use a simple loop for each of the three primes, which is efficient and easy to understand. This approach avoids the need for complex factorization logic or prime generation.

Example Walkthrough

Let’s walk through an example with n = 30:

• Start with n = 30.
• Divide by 2: 30 / 2 = 15.
• Divide by 3: 15 / 3 = 5.
• Divide by 5: 5 / 5 = 1.
• Now n is 1, so 30 is an ugly number.

Another example, n = 14:

• Start with n = 14.
• Divide by 2: 14 / 2 = 7.
• 7 is not divisible by 3 or 5, and we’re left with 7.
• Since 7 is not 1, 14 is not an ugly number.

Time and Space Complexity

• Brute-force approach: Factorizing n and checking all possible divisors up to sqrt(n) would take O(sqrt(n)) time.
• Optimized approach (used here): We only divide by 2, 3, and 5, so the number of divisions is at most log₂(n) + log₃(n) + log₅(n), which is O(log n) in the worst case.
• Space complexity: Both approaches use O(1) extra space, as we only need a few variables.

Summary

The Ugly Number problem is elegantly solved by repeatedly dividing the input by 2, 3, and 5. If the result is 1, it’s ugly; otherwise, it’s not. This approach is efficient, easy to implement, and leverages the problem’s constraints for a straightforward solution.