Ugly Number

How it works

An ugly number has only 2, 3, and 5 as prime factors. This means if we keep dividing the number by 2, 3, and 5 (as long as it is divisible), we should eventually reach 1. If any other prime factor exists, the number will not reduce to 1.

Steps

1. Handle edge case: if n <= 0, return false (ugly numbers are positive).
2. For each prime factor in [2, 3, 5]:
   • While n is divisible by the prime, divide n by it.
3. After all divisions, check if n == 1.
4. Return true if n is 1, false otherwise.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Forgetting to Handle Non-Positive Numbers

Ugly numbers are defined as positive integers. A common mistake is not checking for n <= 0 at the start, which can lead to infinite loops when trying to divide zero or incorrect results for negative numbers. Always return false immediately for non-positive inputs.

Dividing by Primes in the Wrong Order

While the order of dividing by 2, 3, and 5 does not affect correctness, some implementations accidentally skip primes or use incorrect loop conditions. Ensure each prime factor is completely divided out before moving to the next one, using a while loop rather than an if statement.

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; p <= 5 && n > 0; p++) {
            while (n % p == 0) {
                n /= p;
            }
        }

        return n == 1;
    }
};