Ugly Number II Interview Question for Google

# Ugly Numbers

This problem asks us to find the nth ugly number, where ugly numbers are positive integers whose prime factors are limited to 2, 3, and 5.

## Brute Force (Inefficient)

A naive approach would be to iterate through all positive integers and check if each number is an ugly number.  However, this is extremely inefficient and would likely time out for larger values of `n`.

```python
def is_ugly(num):
    if num <= 0:
        return False
    while num % 2 == 0:
        num //= 2
    while num % 3 == 0:
        num //= 3
    while num % 5 == 0:
        num //= 5
    return num == 1

def nth_ugly_number_brute_force(n):
    count = 0
    num = 1
    while count < n:
        if is_ugly(num):
            count += 1
        num += 1
    return num - 1

# Example usage (for demonstration - very slow for larger n)
n = 10
print(f"The {n}th ugly number (brute force) is: {nth_ugly_number_brute_force(n)}")

Optimal Solution (Dynamic Programming)

A more efficient solution uses dynamic programming. We maintain an array of ugly numbers and three pointers, one for each prime factor (2, 3, and 5). At each step, we find the minimum of the next multiples of 2, 3, and 5, add it to the array, and increment the corresponding pointer(s).

def nth_ugly_number(n):
    ugly_numbers = [1] * n
    p2 = p3 = p5 = 0
    
    for i in range(1, n):
        next_multiple_2 = ugly_numbers[p2] * 2
        next_multiple_3 = ugly_numbers[p3] * 3
        next_multiple_5 = ugly_numbers[p5] * 5
        
        ugly_numbers[i] = min(next_multiple_2, next_multiple_3, next_multiple_5)
        
        if ugly_numbers[i] == next_multiple_2:
            p2 += 1
        if ugly_numbers[i] == next_multiple_3:
            p3 += 1
        if ugly_numbers[i] == next_multiple_5:
            p5 += 1
            
    return ugly_numbers[n - 1]

# Example usage
n = 10
print(f"The {n}th ugly number is: {nth_ugly_number(n)}")

n = 1
print(f"The {n}th ugly number is: {nth_ugly_number(n)}")

Big O Runtime Analysis

The optimal solution using dynamic programming has a time complexity of O(n). This is because we iterate n times to build the array of ugly numbers. Inside the loop, we perform a constant number of comparisons and assignments.

The brute force solution's time complexity is much worse. The is_ugly function has a time complexity of O(log n), because in the worst case, num is only divisible by 2,3 or 5. The nth_ugly_number function iterates from 1 to the nth ugly number, which, in the worst case, will require checking all numbers until we reach the nth ugly number, so the overall time complexity is O(N log N), where N is the nth ugly number.

Big O Space Usage Analysis

The optimal solution has a space complexity of O(n) because we store an array of n ugly numbers.

The brute force method has a space complexity of O(1), since only a fixed amount of space is used for variables.

Edge Cases

n = 1: The first ugly number is 1. The dynamic programming solution correctly handles this case.
Large n: The problem statement specifies that 1 <= n <= 1690. The dynamic programming solution efficiently calculates the nth ugly number within this range.
Negative n or n = 0: The problem statement specifies n is a positive integer. If the input were invalid, we would need to add input validation to the code.