# two standard dp solutions

• ``````// three lists:
// (1) 1×2, 2×2, 3×2, 4×2, 5×2, …
// (2) 1×3, 2×3, 3×3, 4×3, 5×3, …
// (3) 1×5, 2×5, 3×5, 4×5, 5×5, …

// O(n) time, O(n) space
int nthUglyNumber(int n) {
vector<int> d(n, 0);
d[0] = 1;

int f2 = 2, f3 = 3, f5 = 5;     // min values for multipy factor 2, 3, 5
int ix2 = 0, ix3 = 0, ix5 = 0;  // indexs for min values of f2, f3, f5

for (int i = 1; i < n; ++i) {
int minV = min(min(f2, f3), f5);
d[i] = minV;

if (minV == f2) f2 = 2 * d[++ix2];
if (minV == f3) f3 = 3 * d[++ix3];
if (minV == f5) f5 = 5 * d[++ix5];
}

return d[n-1];
}

// O(n) (might be more) time, O(3n) space
int nthUglyNumber1(int n) {
queue<int> q1, q2, q3;
q1.push(1), q2.push(1), q3.push(1);

int m = 0;
for (int i = 0; i < n; ++i) {
m = min(min(q1.front(), q2.front()), q3.front());
if (m == q1.front()) q1.pop();
if (m == q2.front()) q2.pop();
if (m == q3.front()) q3.pop();
q1.push(2*m);
q2.push(3*m);
q3.push(5*m);
}

return m;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.