Naive Approach: Brute Force

The brute force approach would involve checking every number starting from 1 until we find the nth ugly number. For each number, we would need to determine if it's an ugly number by repeatedly dividing by 2, 3, and 5 until the number becomes 1. If it becomes 1, then it's an ugly number; otherwise, it's not.

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
        if count == n:
          return num
        num += 1
    return num

Big(O) Complexity:

• Time Complexity: O(n * K), where n is the nth ugly number, and K is the time complexity of is_ugly(). In the worst case, is_ugly() can take O(log n) time, where n is the number being checked.
• Space Complexity: O(1). Constant extra space is used.

Optimal Approach: Dynamic Programming

A more efficient approach uses dynamic programming to build the sequence of ugly numbers. We can maintain an array of ugly numbers and three pointers, one for each prime factor (2, 3, and 5). In each iteration, we select the smallest of the next multiples of 2, 3, and 5 from the current ugly numbers, add it to the sequence, and increment the corresponding pointer.

def nth_ugly_number(n):
    ugly = [0] * n
    ugly[0] = 1
    i2 = i3 = i5 = 0
    next_multiple_of_2 = 2
    next_multiple_of_3 = 3
    next_multiple_of_5 = 5

    for i in range(1, n):
        ugly[i] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)

        if ugly[i] == next_multiple_of_2:
            i2 += 1
            next_multiple_of_2 = ugly[i2] * 2

        if ugly[i] == next_multiple_of_3:
            i3 += 1
            next_multiple_of_3 = ugly[i3] * 3

        if ugly[i] == next_multiple_of_5:
            i5 += 1
            next_multiple_of_5 = ugly[i5] * 5

    return ugly[n - 1]

Big(O) Complexity:

• Time Complexity: O(n), where n is the input. We iterate n times to build the sequence of ugly numbers.
• Space Complexity: O(n), to store the ugly number sequence.

Edge Cases:

• n = 1: The first ugly number is 1.
• n is a larger number: The algorithm efficiently generates ugly numbers up to the nth position.