235. Ugly Number
An ugly number is a positive integer whose prime factorization uses no primes other than 2, 3, and 5. The sequence begins 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, … — and yes, 1 counts, because it has no prime factors at all, so nothing outside the allowed set appears.
You receive a single integer n, which may be zero or negative. Return true if n is an ugly number and false otherwise. Zero and negative integers are never ugly.
Can you decide the answer without computing the full prime factorization?
Example 1:
Input: n = 6
Output: true
Explanation: 6 = 2 × 3 — every prime involved is in {2, 3, 5}, so 6 is ugly.
Example 2:
Input: n = 1
Output: true
Explanation: 1 has no prime factors, so no forbidden prime can appear. It counts as ugly by definition.
Example 3:
Input: n = 14
Output: false
Explanation: 14 = 2 × 7. The prime 7 is outside {2, 3, 5}, so 14 is not ugly.
Constraints:
- -2³¹ ≤ n ≤ 2³¹ - 1
Hints:
If an ugly number is divisible by 2, dividing it by 2 leaves another ugly number. The same is true for 3 and 5 — so keep dividing while you can.
Strip out every factor of 2, then every factor of 3, then every factor of 5. If the original number was ugly, exactly 1 remains; anything larger means some other prime survived the stripping.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 6
Expected output: true