Ugly Number

Difficulty: Easy | Acceptance: 43.50% | Paid: No Topics: Math

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

• Examples
• Constraints
• Iterative Division
• Recursive Division
• Sequential Division

Examples

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Input: n = 1
Output: true
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

Constraints

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

Iterative Division

Intuition We can repeatedly divide the number by 2, 3, and 5 as long as it is divisible by these numbers. If the remaining number is 1, then it only contained these prime factors.

Steps

• If n is less than or equal to 0, return false.
• Iterate through the prime factors [2, 3, 5].
• For each factor, use a while loop to divide n by the factor as long as n is divisible by it.
• After processing all factors, check if n is equal to 1.

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

Complexity

• Time: O(log n) - In the worst case, we divide by 2 repeatedly.
• Space: O(1) - We use a constant amount of extra space.
• Notes: This is the most standard and efficient approach for this problem.

Recursive Division

Intuition We can solve this problem recursively by checking if the number is divisible by 2, 3, or 5. If it is, we recursively check the quotient. The base cases are n == 1 (true) and n <= 0 (false).

Steps

• If n is 1, return true.
• If n is less than or equal to 0, return false.
• If n is divisible by 2, return the result of isUgly(n / 2).
• If n is divisible by 3, return the result of isUgly(n / 3).
• If n is divisible by 5, return the result of isUgly(n / 5).
• If none of the above, return false.

class Solution:
    def isUgly(self, n: int) -> bool:
        if n == 1:
            return True
        if n <= 0:
            return False
        if n % 2 == 0:
            return self.isUgly(n // 2)
        if n % 3 == 0:
            return self.isUgly(n // 3)
        if n % 5 == 0:
            return self.isUgly(n // 5)
        return False

Complexity

• Time: O(log n) - Similar to the iterative approach, depth depends on how many times we can divide.
• Space: O(log n) - Recursion stack space is proportional to the number of divisions.
• Notes: While elegant, the recursive approach uses more stack memory than the iterative one.

Sequential Division

Intuition Instead of iterating through a list of factors, we can explicitly write out the division steps for 2, 3, and 5 in sequence. This removes the overhead of a loop or array iteration, though the complexity remains the same.

Steps

• If n is less than or equal to 0, return false.
• While n is divisible by 2, divide n by 2.
• While n is divisible by 3, divide n by 3.
• While n is divisible by 5, divide n by 5.
• Return true if n is 1, otherwise false.

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

Complexity

• Time: O(log n) - We perform divisions until n is no longer divisible by 2, 3, or 5.
• Space: O(1) - Constant space usage.
• Notes: This is often the fastest in practice due to lack of loop overhead and branch prediction.