LeetCode 263 - Ugly Number

LeetCode Problem 263

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to determine whether a given integer n is an ugly number.

An ugly number is defined as a positive integer whose prime factors are limited to only 2, 3, and 5. This means that after completely factoring the number into primes, every prime factor must belong to the set {2, 3, 5}.

For example:

• 6 is ugly because 6 = 2 × 3
• 8 is ugly because 8 = 2 × 2 × 2
• 30 is ugly because 30 = 2 × 3 × 5
• 14 is not ugly because 14 = 2 × 7, and 7 is not allowed

The input is a single integer n, and the output is a boolean value:

• Return true if n is ugly
• Return false otherwise

One important detail is that ugly numbers must be positive. Negative numbers and zero are automatically not ugly.

The constraints allow values from -2^31 to 2^31 - 1. This tells us that the input fits within a standard 32-bit signed integer range. Since only one number is processed, we do not need to worry about large datasets or memory-heavy solutions. The focus is purely on mathematical correctness and edge case handling.

Several edge cases are especially important:

• n <= 0 should immediately return false
• n = 1 should return true, because 1 has no prime factors, and therefore does not violate the condition
• Numbers containing any prime factor other than 2, 3, or 5 must return false
• Large powers such as 2^30 should still work efficiently

Approaches

Brute Force Approach

A brute-force strategy would attempt to fully factor the number into primes and then verify whether every discovered prime factor belongs to {2, 3, 5}.

The process would involve checking divisibility starting from 2 up to sqrt(n), repeatedly dividing out factors whenever possible. After collecting all prime factors, we would inspect them to ensure no disallowed prime exists.

This approach is correct because prime factorization uniquely identifies all prime divisors of a number. If even one prime factor is not 2, 3, or 5, the number cannot be ugly.

However, this approach performs unnecessary work. We do not actually care about all prime factors. We only need to know whether factors other than 2, 3, and 5 exist. Performing full prime factorization is more expensive than needed.

Optimal Approach

The key observation is that ugly numbers can be completely reduced to 1 by repeatedly dividing by 2, 3, and 5.

For example:

• 30 → 15 → 5 → 1
• 8 → 4 → 2 → 1

If after removing all factors of 2, 3, and 5 the remaining value becomes 1, then the number contains no other prime factors and is ugly.

If some other factor exists, the reduction process will stop at a value greater than 1.

For example:

• 14 → 7
• 7 cannot be divided by 2, 3, or 5
• Since the remaining value is not 1, the number is not ugly

This approach is much simpler and more efficient because it only checks the relevant factors.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(√n)	O(1)	Performs general prime factorization
Optimal	O(log n)	O(1)	Repeatedly removes factors of 2, 3, and 5

Algorithm Walkthrough

1. First, check whether n is positive.

Ugly numbers must be positive integers. If n <= 0, immediately return false. 2. Repeatedly divide by 2 while possible.

If the number is divisible by 2, divide it by 2 until it is no longer divisible. This removes all occurrences of the prime factor 2. 3. Repeatedly divide by 3 while possible.

Apply the same process for factor 3. 4. Repeatedly divide by 5 while possible.

Apply the same process for factor 5. 5. Check the final remaining value.

If all prime factors were only 2, 3, and 5, the number will eventually reduce to 1.

If any other prime factor existed, some value greater than 1 will remain. 6. Return whether the final value equals 1.

Why it works

Every integer has a unique prime factorization. By repeatedly dividing out all factors of 2, 3, and 5, we remove every allowed prime factor from the number.

If the remaining value is 1, then no disallowed prime factors existed. Otherwise, the remaining value must contain some other prime factor, meaning the number is not ugly.

This invariant guarantees correctness.

Python Solution

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False

        for factor in [2, 3, 5]:
            while n % factor == 0:
                n //= factor

        return n == 1

The implementation begins by handling invalid inputs. Since ugly numbers must be positive, any value less than or equal to zero immediately returns False.

Next, the code iterates through the allowed prime factors: 2, 3, and 5.

For each factor, a while loop repeatedly divides n as long as the division is exact. This removes all occurrences of that prime factor from the number.

For example, if n = 72:

• Divide by 2 repeatedly:

• 72 → 36 → 18 → 9

• Divide by 3 repeatedly:

• 9 → 3 → 1

Finally, the algorithm checks whether the remaining value is 1.

If the result is 1, then every prime factor belonged to {2, 3, 5}. Otherwise, another prime factor must have existed.

Go Solution

func isUgly(n int) bool {
    if n <= 0 {
        return false
    }

    factors := []int{2, 3, 5}

    for _, factor := range factors {
        for n%factor == 0 {
            n /= factor
        }
    }

    return n == 1
}

The Go implementation follows the same logic as the Python solution.

One small difference is the use of a slice []int{2, 3, 5} to iterate through the valid factors. Integer division in Go automatically truncates toward zero, which is exactly what we want here.

No special overflow handling is required because all operations reduce the value of n, and the input already fits within the integer range.

Worked Examples

Example 1: n = 6

Initial value:

Step	Operation	n
Start	Initial value	6
Divide by 2	6 ÷ 2	3
Divide by 3	3 ÷ 3	1
Final	n == 1	True

Result: true

Example 2: n = 1

Initial value:

Step	Operation	n
Start	Initial value	1
Divide by 2	Not divisible	1
Divide by 3	Not divisible	1
Divide by 5	Not divisible	1
Final	n == 1	True

Result: true

This works because 1 has no prime factors.

Example 3: n = 14

Initial value:

Step	Operation	n
Start	Initial value	14
Divide by 2	14 ÷ 2	7
Divide by 3	Not divisible	7
Divide by 5	Not divisible	7
Final	n != 1	False

Result: false

The remaining value 7 indicates a disallowed prime factor.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each division reduces the number significantly
Space	O(1)	Only a few variables are used

The time complexity is logarithmic because repeated division continuously shrinks the number. In the worst case, such as powers of 2, the loop executes approximately log₂(n) times.

The space complexity is constant because no extra data structures proportional to the input size are allocated.

Test Cases

solution = Solution()

assert solution.isUgly(6) == True      # standard ugly number
assert solution.isUgly(1) == True      # edge case: 1 is ugly
assert solution.isUgly(14) == False    # contains prime factor 7

assert solution.isUgly(8) == True      # power of 2
assert solution.isUgly(25) == True     # power of 5
assert solution.isUgly(45) == True     # multiple allowed factors

assert solution.isUgly(7) == False     # prime not allowed
assert solution.isUgly(21) == False    # contains factor 7

assert solution.isUgly(0) == False     # zero is not positive
assert solution.isUgly(-6) == False    # negative numbers are invalid

assert solution.isUgly(2**30) == True  # very large power of 2
assert solution.isUgly(2147483647) == False  # large prime number

Test	Why
6	Basic valid ugly number
1	Special edge case with no prime factors
14	Contains invalid factor 7
8	Repeated division by 2
25	Repeated division by 5
45	Combination of valid factors
7	Single invalid prime
21	Mixed valid and invalid factors
0	Non-positive input
-6	Negative number handling
2**30	Large valid input
2147483647	Large invalid prime

Edge Cases

Input is Zero

Zero is a common source of bugs because it is divisible by every nonzero integer. A naive implementation that repeatedly divides factors could accidentally enter incorrect logic or infinite loops.

The implementation avoids this issue by immediately returning False whenever n <= 0.

Input is One

The value 1 is a special mathematical case because it has no prime factors. Some implementations mistakenly return False because no divisions occur.

The algorithm correctly returns True because after attempting to divide by 2, 3, and 5, the value remains 1.

Number Contains an Extra Prime Factor

Numbers like 14, 22, or 77 contain at least one prime factor outside {2, 3, 5}.

The implementation correctly detects this because removing all allowed factors still leaves a value greater than 1.

For example:

• 14 → 7
• Remaining value is 7
• Since 7 != 1, the result is False

Large Powers of Allowed Factors

Values like 2^30 or 5^20 test whether repeated division remains efficient.

Because each division substantially reduces the number, the algorithm handles these cases efficiently in logarithmic time without extra memory usage.