The idea is to use an array to store the ugly numbers and use three pointers for 2, 3, and 5 to calculate the next potential ugly numbers. We then choose the minimum of these numbers to be the next ugly number and appropriately move the pointers.
Time Complexity: O(n), where n is the number of ugly numbers to generate.
Space Complexity: O(n), for storing the ugly numbers array.
1def nthUglyNumber(n):
2 ugly = [0] * n
3 ugly[0] = 1
4 i2, i3, i5 = 0, 0, 0
5 next_2, next_3, next_5 = 2, 3, 5
6
7 for i in range(1, n):
8 next_ugly = min(next_2, next_3, next_5)
9 ugly[i] = next_ugly
10
11 if next_ugly == next_2:
12 i2 += 1
13 next_2 = ugly[i2] * 2
14 if next_ugly == next_3:
15 i3 += 1
16 next_3 = ugly[i3] * 3
17 if next_ugly == next_5:
18 i5 += 1
19 next_5 = ugly[i5] * 5
20
21 return ugly[-1]
22
23n = 10
24print(nthUglyNumber(n)) # Output: 12
25The Python solution uses a list to store ugly numbers and three indices corresponding to the factors 2, 3, and 5. In each iteration, it calculates the next potential ugly numbers, updates the array, and adjusts the indices accordingly.
This method involves using a min-heap to manage the sequence of potential ugly numbers. We start with 1 in the min-heap and repeatedly extract the smallest element, multiplying it by 2, 3, and 5 to generate new candidates, which are then inserted back into the heap. Duplicate entries are avoided by using a set for tracking which numbers have been added to the heap.
Time Complexity: O(n log n), primarily due to heap operations.
Space Complexity: O(n), for data structures that might store up to n numbers.
1import heapq
2
3def nthUglyNumber(n):
4 min_heap = [1]
5 seen = {1}
6
7 for _ in range(n):
8 curr_ugly = heapq.heappop(min_heap)
9 for factor in [2, 3, 5]:
10 new_ugly = curr_ugly * factor
11 if new_ugly not in seen:
12 seen.add(new_ugly)
13 heapq.heappush(min_heap, new_ugly)
14 return curr_ugly
15
16n = 10
17print(nthUglyNumber(n)) # Output: 12
18The Python solution leverages a min-heap for ordering ugly numbers. The smallest number is removed in each iteration and multiplied by 2, 3, and 5 to yield potential new ugly numbers. Tracking entries in a set prevents duplicates in the heap.