LeetCodee

264. Ugly Number II

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the n^th ugly number.

Example 1:

Input: n = 10
Output: 12
Explanation: [1,2,3,4,5,6,8,9,10,12] is the sequence of the first 10 ugly numbers.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints:

1 <= n <= 1690

Solution

Python Solution

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # Initialize array to store ugly numbers
        ugly = [1]
        
        # Initialize pointers for 2, 3, and 5
        i2 = i3 = i5 = 0
        
        # Generate ugly numbers
        while len(ugly) < n:
            # Get next candidates
            next2 = ugly[i2] * 2
            next3 = ugly[i3] * 3
            next5 = ugly[i5] * 5
            
            # Get minimum of candidates
            next_ugly = min(next2, next3, next5)
            
            # Move pointers
            if next_ugly == next2:
                i2 += 1
            if next_ugly == next3:
                i3 += 1
            if next_ugly == next5:
                i5 += 1
                
            ugly.append(next_ugly)
            
        return ugly[-1]

Time Complexity: O(n)

We need to generate n ugly numbers.

Space Complexity: O(n)

We need to store n ugly numbers.

Java Solution

class Solution {
    public int nthUglyNumber(int n) {
        // Initialize array to store ugly numbers
        int[] ugly = new int[n];
        ugly[0] = 1;
        
        // Initialize pointers for 2, 3, and 5
        int i2 = 0, i3 = 0, i5 = 0;
        
        // Generate ugly numbers
        for (int i = 1; i < n; i++) {
            // Get next candidates
            int next2 = ugly[i2] * 2;
            int next3 = ugly[i3] * 3;
            int next5 = ugly[i5] * 5;
            
            // Get minimum of candidates
            int nextUgly = Math.min(next2, Math.min(next3, next5));
            
            // Move pointers
            if (nextUgly == next2) i2++;
            if (nextUgly == next3) i3++;
            if (nextUgly == next5) i5++;
            
            ugly[i] = nextUgly;
        }
        
        return ugly[n - 1];
    }
}

Time Complexity: O(n)

We need to generate n ugly numbers.

Space Complexity: O(n)

We need to store n ugly numbers.

C++ Solution

class Solution {
public:
    int nthUglyNumber(int n) {
        // Initialize array to store ugly numbers
        vector ugly(n);
        ugly[0] = 1;
        
        // Initialize pointers for 2, 3, and 5
        int i2 = 0, i3 = 0, i5 = 0;
        
        // Generate ugly numbers
        for (int i = 1; i < n; i++) {
            // Get next candidates
            int next2 = ugly[i2] * 2;
            int next3 = ugly[i3] * 3;
            int next5 = ugly[i5] * 5;
            
            // Get minimum of candidates
            int nextUgly = min({next2, next3, next5});
            
            // Move pointers
            if (nextUgly == next2) i2++;
            if (nextUgly == next3) i3++;
            if (nextUgly == next5) i5++;
            
            ugly[i] = nextUgly;
        }
        
        return ugly[n - 1];
    }
};

Time Complexity: O(n)

We need to generate n ugly numbers.

Space Complexity: O(n)

We need to store n ugly numbers.

JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function(n) {
    // Initialize array to store ugly numbers
    const ugly = [1];
    
    // Initialize pointers for 2, 3, and 5
    let i2 = 0, i3 = 0, i5 = 0;
    
    // Generate ugly numbers
    while (ugly.length < n) {
        // Get next candidates
        const next2 = ugly[i2] * 2;
        const next3 = ugly[i3] * 3;
        const next5 = ugly[i5] * 5;
        
        // Get minimum of candidates
        const nextUgly = Math.min(next2, next3, next5);
        
        // Move pointers
        if (nextUgly === next2) i2++;
        if (nextUgly === next3) i3++;
        if (nextUgly === next5) i5++;
        
        ugly.push(nextUgly);
    }
    
    return ugly[n - 1];
};

Time Complexity: O(n)

We need to generate n ugly numbers.

Space Complexity: O(n)

We need to store n ugly numbers.

C# Solution

public class Solution {
    public int NthUglyNumber(int n) {
        // Initialize array to store ugly numbers
        int[] ugly = new int[n];
        ugly[0] = 1;
        
        // Initialize pointers for 2, 3, and 5
        int i2 = 0, i3 = 0, i5 = 0;
        
        // Generate ugly numbers
        for (int i = 1; i < n; i++) {
            // Get next candidates
            int next2 = ugly[i2] * 2;
            int next3 = ugly[i3] * 3;
            int next5 = ugly[i5] * 5;
            
            // Get minimum of candidates
            int nextUgly = Math.Min(next2, Math.Min(next3, next5));
            
            // Move pointers
            if (nextUgly == next2) i2++;
            if (nextUgly == next3) i3++;
            if (nextUgly == next5) i5++;
            
            ugly[i] = nextUgly;
        }
        
        return ugly[n - 1];
    }
}

Time Complexity: O(n)

We need to generate n ugly numbers.

Space Complexity: O(n)

We need to store n ugly numbers.

Approach Explanation

The solution uses dynamic programming with three pointers:

Key Insight:
- Every ugly number is a product of smaller ugly numbers
- Use three pointers for multiplying by 2, 3, and 5
- Generate numbers in sorted order
Algorithm Steps:
- Start with first ugly number (1)
- Generate next candidates by multiplying with 2, 3, 5
- Take minimum of candidates
- Move pointers accordingly

Example walkthrough for first few numbers:

Start: [1], i2=i3=i5=0
Candidates: 1×2=2, 1×3=3, 1×5=5 → Add 2
Candidates: 2×2=4, 1×3=3, 1×5=5 → Add 3
Candidates: 2×2=4, 2×3=6, 1×5=5 → Add 4
And so on...

Key insights:

Numbers are generated in sorted order
Multiple pointers may move for same value
Efficient dynamic programming approach
No need to check primality

Edge Cases:

n = 1 (first number)
Duplicate numbers
Integer overflow considerations
Maximum n value (1690)