algoadvance

The problem is to find the nth “ugly number.” In this context, ugly numbers are positive integers whose prime factors only include 2, 3, or 5. The sequence of ugly numbers starts with 1, followed by numbers such as 2, 3, 4, 5, 6, 8, and so on.

Given an integer n, return the nth ugly number in this sequence.

Example:

• Input: n = 10
• Output: 12
• Explanation: The sequence of the first 10 ugly numbers is [1, 2, 3, 4, 5, 6, 8, 9, 10, 12].

Clarifying Questions

1. Range of n: What are the constraints for n? (This helps to understand the efficiency required)
2. Handling Large Inputs: Are we optimizing for extremely large values of n?

Strategy

To solve this problem, we will use a dynamic programming approach involving “merging” three sequences:

1. Multiples of 2
2. Multiples of 3
3. Multiples of 5

Steps

1. Initialization:
   • Start with an array uglies containing the first ugly number, 1.
   • Use three indices to keep track of the next multiples of 2, 3, and 5.
2. Dynamic Programming:
   • Iterate from 1 to n, find the minimum of the next multiples of 2, 3, and 5.
   • Add this minimum value to the uglies list.
   • Update the indices for the multiples that matched the minimum value.
     • If the minimum value is a multiple of 2, move the index corresponding to 2 ahead.
     • Do the same for multiples of 3 and 5.
3. Result:
   • The nth ugly number will be the last element in the uglies array.

Code Implementation

def nthUglyNumber(n: int) -> int:
    uglies = [1]
    i2 = i3 = i5 = 0

    for i in range(1, n):
        next2, next3, next5 = uglies[i2] * 2, uglies[i3] * 3, uglies[i5] * 5
        next_ugly = min(next2, next3, next5)
        uglies.append(next_ugly)

        if next_ugly == next2:
            i2 += 1
        if next_ugly == next3:
            i3 += 1
        if next_ugly == next5:
            i5 += 1

    return uglies[-1]

# Example Usage
n = 10
print(nthUglyNumber(n))  # Output: 12

Time Complexity

• Time Complexity: O(n)
  • We are iterating from 1 to n, performing constant-time operations within each iteration.
• Space Complexity: O(n)
  • We use an array to store the first n ugly numbers.

This solution should efficiently handle constraints typically given in coding problems on platforms like LeetCode.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?