DSA problem
Ugly Number
An ugly number is a positive integer whose only prime factors are limited to 2, 3, and 5. Given an integer n, return true if n is an ugly number, and false otherwise. By convention, 1 is considered ugly because it has no prime factors at all.
The mathematical characterization is simple: n is ugly if and only if it can be written as 2^a * 3^b * 5^c for some non-negative integers a, b, c. Negative numbers, zero, and any number containing a prime factor other than 2, 3, or 5 (for example 7, 11, 13, 14, 21) are not ugly.
The straightforward way to test this is repeated division. As long as n is divisible by 2, divide it by 2. Then do the same for 3, and then for 5. After stripping out all factors of 2, 3, and 5, whatever remains must be either 1 (in which case the original was ugly) or some other prime factor that we could not remove (in which case it was not ugly).
This loop runs O(log n) times overall because each division at least halves the number (for the factor 2) or divides it by 3 or 5. Memory use is O(1). The only edge case is n ≤ 0, which is never ugly and must be rejected immediately.
Examples
n = 6truen = 1truen = 14falseConstraints
- -2^31 <= n <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.