Ugly Number II

Problem

Ugly numbers have only prime factors 2, 3, 5. Return the nth ugly number.

Key insight: Merge three sorted streams: ugly[i]*2, ugly[j]*3, ugly[k]*5. Three-pointer DP.

Solutions

// C
int nthUglyNumber(int n) {
    int* ugly = malloc(n * sizeof(int));
    ugly[0] = 1;
    int i2=0, i3=0, i5=0;
    for (int i = 1; i < n; i++) {
        int n2=ugly[i2]*2, n3=ugly[i3]*3, n5=ugly[i5]*5;
        int mn = n2<n3?n2:n3; mn=mn<n5?mn:n5;
        ugly[i] = mn;
        if (mn==n2) i2++;
        if (mn==n3) i3++;
        if (mn==n5) i5++;
    }
    int res = ugly[n-1];
    free(ugly);
    return res;
}

// C++
int nthUglyNumber(int n) {
    vector<int> ugly(n);
    ugly[0] = 1;
    int i2=0, i3=0, i5=0;
    for (int i = 1; i < n; i++) {
        int next = min({ugly[i2]*2, ugly[i3]*3, ugly[i5]*5});
        ugly[i] = next;
        if (next == ugly[i2]*2) i2++;
        if (next == ugly[i3]*3) i3++;
        if (next == ugly[i5]*5) i5++;
    }
    return ugly[n-1];
}

// Java
public int nthUglyNumber(int n) {
    int[] ugly = new int[n];
    ugly[0] = 1;
    int i2=0, i3=0, i5=0;
    for (int i = 1; i < n; i++) {
        int next = Math.min(ugly[i2]*2, Math.min(ugly[i3]*3, ugly[i5]*5));
        ugly[i] = next;
        if (next == ugly[i2]*2) i2++;
        if (next == ugly[i3]*3) i3++;
        if (next == ugly[i5]*5) i5++;
    }
    return ugly[n-1];
}

// JavaScript
function nthUglyNumber(n) {
    const ugly = [1];
    let i2=0, i3=0, i5=0;
    for (let i = 1; i < n; i++) {
        const next = Math.min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5);
        ugly.push(next);
        if (next === ugly[i2]*2) i2++;
        if (next === ugly[i3]*3) i3++;
        if (next === ugly[i5]*5) i5++;
    }
    return ugly[n-1];
}

# Python
def nthUglyNumber(n):
    ugly = [1]
    i2 = i3 = i5 = 0
    for _ in range(n - 1):
        next_val = min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
        ugly.append(next_val)
        if next_val == ugly[i2] * 2: i2 += 1
        if next_val == ugly[i3] * 3: i3 += 1
        if next_val == ugly[i5] * 5: i5 += 1
    return ugly[-1]

Complexity

Time: O(n)
Space: O(n)

Key Insight

Three pointers simulate three sorted sequences. Increment ALL pointers whose next value equals the chosen minimum (handles duplicates like 6 = 2×3 = 3×2).