Ugly Number II

medium heap dp math

Problem

An ugly number has only 2, 3, and 5 as prime factors. Given n, return the n-th ugly number (1 is considered ugly).

Inputn = 10

Output12

Sequence: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. Three pointers (i2, i3, i5) emit the next value as min(2·u[i2], 3·u[i3], 5·u[i5]).

def nth_ugly_number(n):
    u = [1]
    i2 = i3 = i5 = 0
    while len(u) < n:
        nxt = min(u[i2] * 2, u[i3] * 3, u[i5] * 5)
        u.append(nxt)
        if nxt == u[i2] * 2: i2 += 1
        if nxt == u[i3] * 3: i3 += 1
        if nxt == u[i5] * 5: i5 += 1
    return u[-1]

function nthUglyNumber(n) {
  const u = [1];
  let i2 = 0, i3 = 0, i5 = 0;
  while (u.length < n) {
    const nxt = Math.min(u[i2] * 2, u[i3] * 3, u[i5] * 5);
    u.push(nxt);
    if (nxt === u[i2] * 2) i2++;
    if (nxt === u[i3] * 3) i3++;
    if (nxt === u[i5] * 5) i5++;
  }
  return u[u.length - 1];
}

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

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

Explanation

An ugly number is built only from the factors 2, 3, and 5. The key insight is that every ugly number is some earlier ugly number multiplied by 2, 3, or 5, so we can grow the list in order instead of testing each integer.

We keep a list u starting at [1] and three pointers i2, i3, i5. At each step the next candidate from each factor is u[i2]*2, u[i3]*3, and u[i5]*5; the next ugly number is the minimum of these three.

After appending that minimum, we advance every pointer whose candidate equaled it. Bumping all matching pointers is what avoids duplicates (for example 6 is both 2*3 and 3*2).

Example: starting from 1 we produce 2, 3, 4, 5, 6, 8, 9, 10, 12. The 10th value is 12.

Each new number costs only a min of three values and a few pointer bumps, so building up to the n-th number is fast and uses no factoring.

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