264. Ugly Number II – Leetcode Solutions

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.

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # We need at least n ugly numbers, so create a list to store them.
        ugly_numbers = [0] * n
        ugly_numbers[0] = 1  # The first ugly number is 1
        
        # Initialize pointers for 2, 3, and 5
        p2, p3, p5 = 0, 0, 0
        
        # Initial multiples for 2, 3, and 5
        next_multiple_of_2 = 2
        next_multiple_of_3 = 3
        next_multiple_of_5 = 5
        
        # Iterate to find all ugly numbers until we reach the nth
        for i in range(1, n):
            # The next ugly number is the minimum of the next multiples
            next_ugly = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
            
            # Add the smallest found ugly number to the list
            ugly_numbers[i] = next_ugly
            
            # Increment the pointer for whichever factor(s) matched the next ugly number
            if next_ugly == next_multiple_of_2:
                p2 += 1
                next_multiple_of_2 = ugly_numbers[p2] * 2
            if next_ugly == next_multiple_of_3:
                p3 += 1
                next_multiple_of_3 = ugly_numbers[p3] * 3
            if next_ugly == next_multiple_of_5:
                p5 += 1
                next_multiple_of_5 = ugly_numbers[p5] * 5
        
        # The nth ugly number is now at the (n-1)th index of the list (0-based index)
        return ugly_numbers[n - 1]

class Solution {
public:
    int nthUglyNumber(int n) {
        // Create a vector to store the first 'n' ugly numbers
        std::vector<int> ugly_numbers(n);
        
        // The first ugly number is defined as 1
        ugly_numbers[0] = 1;
        
        // Pointers to track the next multiples of 2, 3, and 5
        int p2 = 0, p3 = 0, p5 = 0;
        
        // Initialize the first multiples of 2, 3, and 5
        int next_multiple_of_2 = 2;
        int next_multiple_of_3 = 3;
        int next_multiple_of_5 = 5;
        
        // Start filling the ugly numbers from the second position to the nth
        for (int i = 1; i < n; i++) {
            // The next ugly number will be the minimum of the three multiples
            int next_ugly = std::min(next_multiple_of_2, std::min(next_multiple_of_3, next_multiple_of_5));
            
            // Add the next ugly number to the list
            ugly_numbers[i] = next_ugly;
            
            // If this ugly number was produced by multiplying with 2, increment pointer p2
            if (next_ugly == next_multiple_of_2) {
                p2++;
                next_multiple_of_2 = ugly_numbers[p2] * 2;
            }
            
            // If this ugly number was produced by multiplying with 3, increment pointer p3
            if (next_ugly == next_multiple_of_3) {
                p3++;
                next_multiple_of_3 = ugly_numbers[p3] * 3;
            }
            
            // If this ugly number was produced by multiplying with 5, increment pointer p5
            if (next_ugly == next_multiple_of_5) {
                p5++;
                next_multiple_of_5 = ugly_numbers[p5] * 5;
            }
        }
        
        // The nth ugly number is now at the (n-1)th index (0-based index)
        return ugly_numbers[n - 1];
    }
};

var nthUglyNumber = function(n) {
    // Create an array to store the first 'n' ugly numbers
    let uglyNumbers = new Array(n);
    
    // The first ugly number is defined as 1
    uglyNumbers[0] = 1;
    
    // Initialize three pointers to track the next multiples of 2, 3, and 5
    let p2 = 0, p3 = 0, p5 = 0;
    
    // Initial multiples for 2, 3, and 5
    let nextMultipleOf2 = 2;
    let nextMultipleOf3 = 3;
    let nextMultipleOf5 = 5;
    
    // Fill the array with the first 'n' ugly numbers
    for (let i = 1; i < n; i++) {
        // The next ugly number is the minimum of the three multiples
        let nextUgly = Math.min(nextMultipleOf2, nextMultipleOf3, nextMultipleOf5);
        
        // Add the next ugly number to the array
        uglyNumbers[i] = nextUgly;
        
        // Increment the corresponding pointer(s) to compute the next multiple
        if (nextUgly === nextMultipleOf2) {
            p2++;
            nextMultipleOf2 = uglyNumbers[p2] * 2;
        }
        
        if (nextUgly === nextMultipleOf3) {
            p3++;
            nextMultipleOf3 = uglyNumbers[p3] * 3;
        }
        
        if (nextUgly === nextMultipleOf5) {
            p5++;
            nextMultipleOf5 = uglyNumbers[p5] * 5;
        }
    }
    
    // The nth ugly number is the last element in the array (0-based index)
    return uglyNumbers[n - 1];
};

class Solution {
    public int nthUglyNumber(int n) {
        // Array to store the first 'n' ugly numbers
        int[] uglyNumbers = new int[n];
        
        // The first ugly number is always 1
        uglyNumbers[0] = 1;
        
        // Initialize three pointers for multiples of 2, 3, and 5
        int p2 = 0, p3 = 0, p5 = 0;
        
        // Initial values for the next multiples of 2, 3, and 5
        int nextMultipleOf2 = 2;
        int nextMultipleOf3 = 3;
        int nextMultipleOf5 = 5;
        
        // Loop to generate the first 'n' ugly numbers
        for (int i = 1; i < n; i++) {
            // The next ugly number is the minimum of the three multiples
            int nextUgly = Math.min(nextMultipleOf2, Math.min(nextMultipleOf3, nextMultipleOf5));
            
            // Store the next ugly number in the array
            uglyNumbers[i] = nextUgly;
            
            // Increment the pointers and update the next multiple as needed
            if (nextUgly == nextMultipleOf2) {
                p2++;
                nextMultipleOf2 = uglyNumbers[p2] * 2;
            }
            if (nextUgly == nextMultipleOf3) {
                p3++;
                nextMultipleOf3 = uglyNumbers[p3] * 3;
            }
            if (nextUgly == nextMultipleOf5) {
                p5++;
                nextMultipleOf5 = uglyNumbers[p5] * 5;
            }
        }
        
        // The nth ugly number is stored in the (n-1)th index (0-based)
        return uglyNumbers[n - 1];
    }
}