Nth Ugly Number

Share

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, ...

Example 1
Input: n=10 → Output: 12
Example 2
Input: n=1 → Output: 1

Solution Approach

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).
Java
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)