Math - Nth Ugly Number

An ugly number is a positive integer whose only prime factors are 2, 3, and 5. Given n, return the nth ugly number. Sequence: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...

Input: n=10 → Output: 12

Input: n=1 → Output: 1

Three-pointer DP: maintain pointers p2, p3, p5 into the ugly number sequence. Next ugly number is min(ugly[p2]*2, ugly[p3]*3, ugly[p5]*5).

dp[0]=1; p2=p3=p5=0.
For i from 1 to n-1: next = min(dp[p2]*2, dp[p3]*3, dp[p5]*5).
Advance each pointer whose product equals next (handle ties to avoid duplicates).

class Solution { public int nthUglyNumber(int n) { int[] dp = new int[n]; dp[0] = 1; int p2=0, p3=0, p5=0; for (int i = 1; i < n; i++) { int next = Math.min(dp[p2]*2, Math.min(dp[p3]*3, dp[p5]*5)); dp[i] = next; if (next == dp[p2]*2) p2++; if (next == dp[p3]*3) p3++; if (next == dp[p5]*5) p5++; } return dp[n-1]; } }

Time Complexity: O(N)
Space Complexity: O(N)