Ugly Number
EasyPrompt
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 × 3Example 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 - 1
Approaches
2 approaches with complexity analysis and trade-offs.
Check if the number has any prime factors other than 2, 3, and 5 by trying to divide by all numbers up to sqrt(n).
Algorithm
- If n ≤ 0, return false as ugly numbers are positive
- For each number i from 2 to sqrt(n):
- While n is divisible by i:
- If i is not 2, 3, or 5, return false
- Divide n by i
- While n is divisible by i:
- If remaining n > 5, return false
- Return true
Walkthrough
This approach involves checking all possible prime factors of the number n by iterating through numbers from 2 to sqrt(n). For each number, we keep dividing n by it as long as possible. If we encounter any prime factor other than 2, 3, or 5, we return false.
public boolean isUgly(int n) { if (n <= 0) return false; // Try dividing by numbers up to sqrt(n) for (int i = 2; i * i <= n; i++) { while (n % i == 0) { // If we find a prime factor other than 2, 3, or 5 if (i != 2 && i != 3 && i != 5) { return false; } n /= i; } } // Check if remaining number is greater than 5 if (n > 5) return false; return true;}Complexity
Time
O(sqrt(n)) - We need to check all numbers up to sqrt(n)
Space
O(1) - Only uses a constant amount of extra space
Trade-offs
Pros
Simple to understand and implement
Works for all input cases
Cons
Not the most efficient solution
Checks unnecessary numbers that aren't prime factors
Solutions
Solution
class Solution {public boolean isUgly(int n) { if (n < 1) return false; while (n % 2 == 0) { n /= 2; } while (n % 3 == 0) { n /= 3; } while (n % 5 == 0) { n /= 5; } return n == 1; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.