Ugly Number - Video Solutions

Problem Overview: Determine whether an integer n is an Ugly Number. A number is considered ugly if its only prime factors are 2, 3, and 5. Negative numbers and zero are never ugly numbers.

The key observation: if you repeatedly divide a valid ugly number by 2, 3, and 5, the result eventually becomes 1. If another prime factor exists (like 7 or 11), the reduction process stops before reaching 1.

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

This approach repeatedly removes the allowed prime factors from n. Start by checking if n <= 0; such numbers cannot be ugly. Then iterate through the factors 2, 3, and 5. For each factor, divide n while it is divisible by that factor using a loop like while (n % factor == 0). After removing all occurrences of these factors, check if the remaining value equals 1. If it does, the number contained only allowed primes.

The number shrinks quickly with each division, so the loop runs at most O(log n) times. Memory usage stays constant because only a few variables are maintained. This approach relies on simple arithmetic operations from math and is the most practical implementation for production code and interviews.

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

The recursive variant follows the same idea but expresses the factor removal using recursive calls. If n is divisible by 2, recursively check n / 2. Otherwise check divisibility by 3, then 5. When n == 1, return true. If none of the divisions apply, return false because another prime factor must exist.

Each recursive call reduces the number by one factor, so the recursion depth is bounded by O(log n). The call stack introduces O(log n) space overhead. This approach highlights clean problem decomposition and fits well when practicing recursion patterns.

Recommended for interviews: The iterative division approach is what most interviewers expect. It demonstrates recognition of the mathematical property behind ugly numbers and produces a concise O(log n) solution with constant space. Mentioning the recursive version still shows strong understanding of factor reduction and problem decomposition within math-based problems.