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
Divide the number repeatedly by 2, 3, and 5 until it can't be divided anymore. If the final number is 1, it's an ugly number.
Algorithm
- If n ≤ 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 equals 1, false otherwise
Walkthrough
This approach focuses only on the prime factors that make a number ugly (2, 3, and 5). We repeatedly divide the number by these factors until we can't anymore. If the final result is 1, then the number only had these prime factors.
public boolean isUgly(int n) { if (n <= 0) return false; // Divide by 2, 3, and 5 as many times as possible int[] factors = {2, 3, 5}; for (int factor : factors) { while (n % factor == 0) { n /= factor; } } return n == 1;}Complexity
Time
O(log n) - Each division reduces the number by at least half
Space
O(1) - Uses constant extra space
Trade-offs
Pros
More efficient than checking all numbers
Only focuses on relevant prime factors
Simple and clean implementation
Cons
Still performs multiple division operations
Might have numerical overflow issues with very large numbers
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; }}/** * @param {number} n * @return {boolean} */ var isUgly = function (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;};class Solution {public: bool 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; }};class Solution: def isUgly(self, n: int) -> bool: if n < 1: return False for x in [2, 3, 5]: while n % x == 0: n //= x return n == 1Video 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.