Ugly Number - Solution & Explanation

Problem Overview: An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return true if repeatedly removing factors of 2, 3, and 5 reduces the number to 1. Any remaining factor means the number is not ugly.

Approach 1: Iterative Division Approach (O(log n) time, O(1) space)

The idea is straightforward: repeatedly divide the number by 2, 3, and 5 while it remains divisible. Start with n, check n % 2, n % 3, and n % 5, and keep dividing in loops until those factors are fully removed. If the final value becomes 1, all prime factors were limited to the allowed set. If anything greater than 1 remains, another prime factor exists and the number is not ugly.

This works because prime factorization is unique. Removing these three primes exhaustively guarantees that any leftover factor must be invalid. The number of operations is proportional to how many times the number can be divided, which is at most logarithmic relative to n. This approach uses constant extra memory and is the most common implementation in coding interviews.

Approach 2: Recursive Division Approach (O(log n) time, O(log n) space)

The recursive version applies the same logic but expresses it through function calls. If n equals 1, return true. Otherwise, if n is divisible by 2, 3, or 5, recursively call the function with n/2, n/3, or n/5. If none of those divisions apply, the number contains another prime factor and the recursion stops with false.

Each recursive call removes one factor, so the recursion depth is bounded by the number of divisions possible, which is O(log n). The algorithm is logically clean and mirrors the mathematical definition of ugly numbers. However, it uses stack space proportional to the recursion depth, which is why iterative solutions are generally preferred.

Both approaches rely on simple number properties rather than advanced data structures. The problem sits squarely in the math category, and the recursive variant also demonstrates patterns from recursion. The key insight is that validating the prime factor set is equivalent to repeatedly stripping the allowed factors.

Recommended for interviews: The iterative division approach. It runs in O(log n) time with O(1) space and avoids recursion overhead. Interviewers usually expect this solution because it directly translates the mathematical definition into efficient code. Implementing the recursive version still demonstrates understanding, but the iterative method shows stronger control over space efficiency.