#263
Ugly Number
Easy Prime factors
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
An ugly number is a positive integer whose only prime factors are 2, 3 and 5. Decide whether n is ugly.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: is n built only from the primes 2, 3 and 5?
Why this works: divide out every 2, 3 and 5. If nothing else was in there, 1 is left.
Example: n = 14
14 / 2 = 77 not divisible by 2, 3, 5left with 7 ≠ 1 → not ugly
✦Hints open one at a time
Non-positive numbers are never ugly.
Divide out all 2s, then all 3s, then all 5s. What should be left?
↗Approach
Repeatedly divide by 2, 3 and 5 while divisible. If what remains is 1, there were no other prime factors.
</>Solution (Java)
class Solution {
public boolean isUgly(int n) {
if (n <= 0) return false;
for (int p : new int[]{2, 3, 5}) {
while (n % p == 0) n /= p;
}
return n == 1;
}
}!Common mistake
Forgetting n <= 0; the while loop on 0 never ends because 0 % 2 == 0.
Complexity
- Time: O(log n).
- Space: O(1).
