Problem Description
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.
Key Insights
- Ugly numbers are defined by their prime factors: only 2, 3, and 5 are allowed.
- The number 1 is considered an ugly number since it has no prime factors.
- Any negative number or zero cannot be an ugly number since they do not meet the positivity criterion.
- We can iteratively divide the number by 2, 3, and 5 until we can no longer do so.
Space and Time Complexity
Time Complexity: O(log n) - In the worst case, we may need to divide the number multiple times by 2, 3, or 5.
Space Complexity: O(1) - We are using a constant amount of space.
Solution
To determine if a number is an ugly number, we can repeatedly divide the number by 2, 3, and 5 as long as it is divisible by these numbers. If, after all possible divisions, we are left with 1, then the number is ugly; otherwise, it is not. This approach uses a simple iterative process with no additional data structures required.