An ugly number is a positive integer which does not have a prime factor other than 2, 3, and 5.
Given an integer n, return true if n is an ugly number.
Example 1:
Input: n = 6 Output: true Explanation: 6 = 2 × 3
Example 2:
Input: n = 1 Output: true Explanation: 1 has no prime factors.
Example 3:
Input: n = 14 Output: false Explanation: 14 is not ugly since it includes the prime factor 7.
Constraints:
-231 <= n <= 231 - 1Problem Overview: Determine whether an integer n is an Ugly Number. A number is considered ugly if its only prime factors are 2, 3, and 5. Negative numbers and zero are never ugly numbers.
The key observation: if you repeatedly divide a valid ugly number by 2, 3, and 5, the result eventually becomes 1. If another prime factor exists (like 7 or 11), the reduction process stops before reaching 1.
Approach 1: Iterative Division Approach (O(log n) time, O(1) space)
This approach repeatedly removes the allowed prime factors from n. Start by checking if n <= 0; such numbers cannot be ugly. Then iterate through the factors 2, 3, and 5. For each factor, divide n while it is divisible by that factor using a loop like while (n % factor == 0). After removing all occurrences of these factors, check if the remaining value equals 1. If it does, the number contained only allowed primes.
The number shrinks quickly with each division, so the loop runs at most O(log n) times. Memory usage stays constant because only a few variables are maintained. This approach relies on simple arithmetic operations from math and is the most practical implementation for production code and interviews.
Approach 2: Recursive Division Approach (O(log n) time, O(log n) space)
The recursive variant follows the same idea but expresses the factor removal using recursive calls. If n is divisible by 2, recursively check n / 2. Otherwise check divisibility by 3, then 5. When n == 1, return true. If none of the divisions apply, return false because another prime factor must exist.
Each recursive call reduces the number by one factor, so the recursion depth is bounded by O(log n). The call stack introduces O(log n) space overhead. This approach highlights clean problem decomposition and fits well when practicing recursion patterns.
Recommended for interviews: The iterative division approach is what most interviewers expect. It demonstrates recognition of the mathematical property behind ugly numbers and produces a concise O(log n) solution with constant space. Mentioning the recursive version still shows strong understanding of factor reduction and problem decomposition within math-based problems.
This approach involves dividing the number by its prime factors (2, 3, and 5) as long as it is divisible by them. If after removing all these factors, the number reduces to 1, it is an ugly number; otherwise, it is not.
This C solution checks if a number is an ugly number by iteratively dividing it by the prime factors 2, 3, and 5. If n is reduced to 1, it returns true, indicating n is an ugly number.
Time Complexity: O(log n).
Space Complexity: O(1).
This alternative approach involves using recursion to systematically divide the number by 2, 3, and 5. By tracing back all divisions reaching 1, this method can also verify the ugliness of a number.
This C function uses recursion to repeatedly divide the number by 2, 3, or 5, checking if the reduced result is 1, confirming the number's ugliness.
Time Complexity: O(log n).
Space Complexity: O(log n), due to recursion stack.
| Approach | Complexity |
|---|---|
| Iterative Division Approach | Time Complexity: O(log n). |
| Recursive Division Approach | Time Complexity: O(log n). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Division | O(log n) | O(1) | Best general solution. Efficient and expected in interviews. |
| Recursive Division | O(log n) | O(log n) | Useful for demonstrating recursion and factor reduction logic. |
Ugly Number - Leetcode 263 - Python • NeetCode • 31,869 views views
Watch 9 more video solutions →Practice Ugly Number with our built-in code editor and test cases.
Practice on FleetCode