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.
1using System;
2
3public class Solution {
4 public int NthUglyNumber(int n) {
5 int[] ugly = new int[n];
6 ugly[0] = 1;
7 int i2 = 0, i3 = 0, i5 = 0;
8 int next_2 = 2, next_3 = 3, next_5 = 5;
9
10 for (int i = 1; i < n; i++) {
11 int next_ugly = Math.Min(next_2, Math.Min(next_3, next_5));
12 ugly[i] = next_ugly;
13
14 if (next_ugly == next_2) next_2 = ugly[++i2] * 2;
15 if (next_ugly == next_3) next_3 = ugly[++i3] * 3;
16 if (next_ugly == next_5) next_5 = ugly[++i5] * 5;
17 }
18 return ugly[n - 1];
19 }
20
21 public static void Main(string[] args) {
22 Solution sol = new Solution();
23 int n = 10;
24 Console.WriteLine(sol.NthUglyNumber(n)); // Output: 12
25 }
26}
27The C# solution mirrors the approach used in the other languages, storing ugly numbers in an array with three pointers for multiples of 2, 3, and 5. It identifies each subsequent ugly number and updates the array.
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.