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.
1public class Main {
2
3 public static int nthUglyNumber(int n) {
4 int[] ugly = new int[n];
5 ugly[0] = 1;
6 int i2 = 0, i3 = 0, i5 = 0;
7 int next_2 = 2, next_3 = 3, next_5 = 5;
8
9 for (int i = 1; i < n; i++) {
10 int next_ugly = Math.min(next_2, Math.min(next_3, next_5));
11 ugly[i] = next_ugly;
12
13 if (next_ugly == next_2) next_2 = ugly[++i2] * 2;
14 if (next_ugly == next_3) next_3 = ugly[++i3] * 3;
15 if (next_ugly == next_5) next_5 = ugly[++i5] * 5;
16 }
17 return ugly[n - 1];
18 }
19
20 public static void main(String[] args) {
21 int n = 10;
22 System.out.println(nthUglyNumber(n)); // Output: 12
23 }
24}
25This Java solution uses an integer array to store the sequence of ugly numbers, with the same logic and three pointers as in the C/C++ solutions. It sequentially generates ugly numbers by multiplying previous numbers by 2, 3, and 5 and selecting the smallest candidate in each iteration.
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.