#264 Ugly Number II - Solution

The goal of #264 Ugly Number II is to find the nth positive number whose prime factors are limited to 2, 3, and 5. A brute force approach that checks every number and factors it would be inefficient for large n. Instead, efficient generation techniques are used.

A common strategy uses dynamic programming with three pointers. The idea is to build the sequence of ugly numbers incrementally. Maintain indices representing the next multiple of 2, 3, and 5. At each step, choose the smallest candidate and advance the corresponding pointer(s). This ensures numbers remain sorted and avoids duplicates.

Another approach uses a min-heap (priority queue) combined with a hash set to repeatedly extract the smallest ugly number and generate its multiples. While simpler conceptually, it introduces additional overhead due to heap operations.

The dynamic programming method is typically preferred because it generates numbers in order with linear time and minimal extra space.

Approach	Time Complexity	Space Complexity
Dynamic Programming (Three Pointers)	O(n)	O(n)
Heap + Hash Set	O(n log n)	O(n)

Solutions (8)

Dynamic Programming with Three Pointers

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.

C C++Java Python C#JavaScript

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
        if (next_ugly == next_2) next_2 = ugly[++i2] * 2;
        if (next_ugly == next_3) next_3 = ugly[++i3] * 3;
        if (next_ugly == next_5) next_5 = ugly[++i5] * 5;
    }
    return ugly[n - 1];
}

int main() {
    int n = 10;
    cout << nthUglyNumber(n) << endl; // Output: 12
    return 0;
}

Explanation

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.

Min-Heap Approach

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.

C++Python

1#include <iostream>
2#include <queue>
3#include <unordered_set>
4using namespace std;
5
int nthUglyNumber(int n) {
    priority_queue<long, vector<long>, greater<long>> minHeap;
    unordered_set<long> seen;
    minHeap.push(1);
    seen.insert(1);
    long currUgly = 1;

    for (int i = 0; i < n; ++i) {
        currUgly = minHeap.top();
        minHeap.pop();
        if (!seen.count(currUgly * 2)) {
            minHeap.push(currUgly * 2);
            seen.insert(currUgly * 2);
        }
        if (!seen.count(currUgly * 3)) {
            minHeap.push(currUgly * 3);
            seen.insert(currUgly * 3);
        }
        if (!seen.count(currUgly * 5)) {
            minHeap.push(currUgly * 5);
            seen.insert(currUgly * 5);
        }
    }
    return (int)currUgly;
}

int main() {
    int n = 10;
    cout << nthUglyNumber(n) << endl; // Output: 12
    return 0;
}