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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int nthUglyNumber(int n) {
6 vector<int> ugly(n);
7 ugly[0] = 1;
8 int i2 = 0, i3 = 0, i5 = 0;
9 int next_2 = 2, next_3 = 3, next_5 = 5;
10
11 for (int i = 1; i < n; ++i) {
12 int next_ugly = min(next_2, min(next_3, next_5));
13 ugly[i] = next_ugly;
14
15 if (next_ugly == next_2) next_2 = ugly[++i2] * 2;
16 if (next_ugly == next_3) next_3 = ugly[++i3] * 3;
17 if (next_ugly == next_5) next_5 = ugly[++i5] * 5;
18 }
19 return ugly[n - 1];
20}
21
22int main() {
23 int n = 10;
24 cout << nthUglyNumber(n) << endl; // Output: 12
25 return 0;
26}This C++ solution follows the dynamic programming approach with three pointers. Here, a vector is used to store the sequence of ugly numbers, and pointers i2, i3, and i5 are used in the same way as described for the C solution, determining the smallest next number and updating corresponding pointers.
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.
1#include <iostream>
2#include <queue>
3#include <unordered_set>
4using namespace std;
5
6int nthUglyNumber(int n) {
7 priority_queue<long, vector<long>, greater<long>> minHeap;
8 unordered_set<long> seen;
9 minHeap.push(1);
10 seen.insert(1);
11 long currUgly = 1;
12
13 for (int i = 0; i < n; ++i) {
14 currUgly = minHeap.top();
15 minHeap.pop();
16 if (!seen.count(currUgly * 2)) {
17 minHeap.push(currUgly * 2);
18 seen.insert(currUgly * 2);
19 }
20 if (!seen.count(currUgly * 3)) {
21 minHeap.push(currUgly * 3);
22 seen.insert(currUgly * 3);
23 }
24 if (!seen.count(currUgly * 5)) {
25 minHeap.push(currUgly * 5);
26 seen.insert(currUgly * 5);
27 }
28 }
29 return (int)currUgly;
30}
31
32int main() {
33 int n = 10;
34 cout << nthUglyNumber(n) << endl; // Output: 12
35 return 0;
36}The solution uses a min-heap to keep track of and retrieve the smallest ugly number, avoiding duplicates by using a set. It generates ugly numbers by multiplying the current smallest number by 2, 3, and 5, inserting valid new numbers back into the heap.