LeetCode 263: Ugly Number

A clear explanation of the Ugly Number problem using repeated division by the only allowed prime factors.

leetcodemathnumber-theory

Problem Restatement

We are given an integer n.

Return True if n is an ugly number.

An ugly number is a positive integer whose prime factors are limited to:

2, 3, 5

So a number is ugly if, after removing all factors of 2, 3, and 5, nothing remains except 1.

The problem constraints are:

-2^31 <= n <= 2^31 - 1

1 is considered ugly because it has no prime factors. Non-positive numbers are not ugly.

Input and Output

Item Meaning
Input An integer n
Output Boolean
Ugly number Positive integer with no prime factors except 2, 3, and 5
Special case 1 is ugly

Example function shape:

def isUgly(n: int) -> bool:
    ...

Examples

Example 1:

n = 6

Prime factorization:

6 = 2 * 3

All prime factors are allowed.

Answer:

True

Example 2:

n = 1

1 has no prime factors.

Since it has no forbidden prime factor, it is ugly.

Answer:

True

Example 3:

n = 14

Prime factorization:

14 = 2 * 7

The factor 7 is not allowed.

Answer:

False

Example 4:

n = 0

Ugly numbers must be positive.

Answer:

False

First Thought: Prime Factorization

A direct way is to factor n into primes, then check whether every prime factor is one of:

2, 3, 5

This works, but full prime factorization is unnecessary.

We do not care what all factors are.

We only care whether any factor remains after removing all 2s, 3s, and 5s.

Key Insight

If n is ugly, then it can be reduced to 1 by repeatedly dividing by 2, 3, and 5.

For example:

n = 30

Divide by 2:

30 / 2 = 15

Divide by 3:

15 / 3 = 5

Divide by 5:

5 / 5 = 1

Since the final value is 1, 30 is ugly.

For a non-ugly number:

n = 14

Divide by 2:

14 / 2 = 7

Now 7 is not divisible by 2, 3, or 5.

The final value is 7, so 14 is not ugly.

Algorithm

  1. If n <= 0, return False.
  2. For each allowed factor p in [2, 3, 5]:
    • While n is divisible by p, divide n by p.
  3. After removing all allowed factors:
    • Return True if n == 1.
    • Otherwise return False.

Walkthrough

Use:

n = 12

Start with allowed factors:

[2, 3, 5]

Divide by 2 while possible:

12 / 2 = 6
6 / 2 = 3

Now 3 is no longer divisible by 2.

Divide by 3:

3 / 3 = 1

Now the value is 1.

Return:

True

Use:

n = 42

Divide by 2:

42 / 2 = 21

Divide by 3:

21 / 3 = 7

7 cannot be divided by 2, 3, or 5.

Return:

False

Correctness

If the algorithm returns True, then after repeatedly dividing by 2, 3, and 5, the remaining value is 1. Therefore the original number was made only from factors 2, 3, and 5. So it has no forbidden prime factor and is ugly.

If the algorithm returns False, then after removing all possible factors of 2, 3, and 5, the remaining value is greater than 1. This remaining value must contain some prime factor other than 2, 3, or 5. Therefore the original number has a forbidden prime factor and is not ugly.

The algorithm also rejects all n <= 0, which is correct because ugly numbers are positive.

Therefore the algorithm returns the correct result.

Complexity

Metric Value Why
Time O(log n) Each division reduces n by at least a factor of 2
Space O(1) Only a few variables are used

Implementation

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

Code Explanation

First handle non-positive input:

if n <= 0:
    return False

This is necessary because ugly numbers are positive.

Then iterate through the only allowed prime factors:

for factor in (2, 3, 5):

For each allowed factor, remove it completely:

while n % factor == 0:
    n //= factor

After all divisions, n == 1 means nothing forbidden remains.

return n == 1

Testing

def run_tests():
    s = Solution()

    assert s.isUgly(6) is True
    assert s.isUgly(1) is True
    assert s.isUgly(14) is False
    assert s.isUgly(0) is False
    assert s.isUgly(-6) is False
    assert s.isUgly(30) is True
    assert s.isUgly(42) is False
    assert s.isUgly(2 ** 10) is True
    assert s.isUgly((2 ** 4) * (3 ** 3) * (5 ** 2)) is True

    print("all tests passed")

run_tests()

Test meaning:

Test Why
6 Uses allowed factors 2 and 3
1 No prime factors
14 Contains forbidden factor 7
0 Non-positive input
-6 Negative input
30 Uses all allowed factors
42 Contains forbidden factor after division
Power of 2 Repeated allowed factor
Product of 2, 3, and 5 Larger ugly number