Ugly Number II

class Solution {
public:
    int findNthUglyNumber(int position) {
        vector<int> uglySequence(position);
        uglySequence[0] = 1;
    
        int ptr2 = 0, ptr3 = 0, ptr5 = 0;
        int value2 = 2, value3 = 3, value5 = 5;
    
        for (int index = 1; index < position; index++) {
            int minUgly = min(value2, min(value3, value5));
            uglySequence[index] = minUgly;
    
            if (minUgly == value2) {
                ptr2++;
                value2 = uglySequence[ptr2] * 2;
            }
            if (minUgly == value3) {
                ptr3++;
                value3 = uglySequence[ptr3] * 3;
            }
            if (minUgly == value5) {
                ptr5++;
                value5 = uglySequence[ptr5] * 5;
            }
        }
    
        return uglySequence[position - 1];
    }
};

The Ugly Number II problem involves finding the n-th ugly number using the C++ programming language. An ugly number is defined as a positive integer whose prime factors are limited to 2, 3, or 5.

The provided C++ solution uses dynamic programming to generate ugly numbers in a systematic manner. The core concept behind the solution is:

• Start by initializing a vector uglySequence with the size equal to position and setting the first element to 1, as the first ugly number is always 1.
• Maintain three pointers ptr2, ptr3, and ptr5 which are associated respectively with factors 2, 3, and 5. These pointers will help us select the next ugly number by multiplying the pointed index's element with 2, 3, and 5.
• As you progress through the numbers, calculate potential candidates for the next ugly number by multiplying the values pointed by ptr2, ptr3, and ptr5 with 2, 3, and 5 respectively.
• Determine the minimum value among these candidates and add it to uglySequence.
• Increment the respective pointers when their candidate value is chosen as the minimum to avoid duplication of the same values.

This method ensures that each next ugly number is the smallest possible new ugly number and efficiently computes the position-th ugly number, which is uglySequence[position - 1].

By using this approach, time is not wasted checking non-ugly numbers and the solutions collector progresses in an optimal manner only considering viable next options.

class Solution {
    
    public int findNthUglyNumber(int n) {
        int[] sequence = new int[n]; // Array to hold the ugly numbers
        sequence[0] = 1; // Initializing the first element
    
        // Indices for the multiples of 2, 3, and 5
        int multiple2Index = 0, multiple3Index = 0, multiple5Index = 0;
        int next2 = 2, next3 = 3, next5 = 5;
    
        // Loop to fill in values up to the nth ugly number
        for (int i = 1; i < n; i++) {
            // Determine the next number to add to the sequence
            int minUgly = Math.min(next2, Math.min(next3, next5));
            sequence[i] = minUgly;
    
            // Advance the necessary pointers
            if (minUgly == next2) {
                multiple2Index++;
                next2 = sequence[multiple2Index] * 2;
            }
            if (minUgly == next3) {
                multiple3Index++;
                next3 = sequence[multiple3Index] * 3;
            }
            if (minUgly == next5) {
                multiple5Index++;
                next5 = sequence[multiple5Index] * 5;
            }
        }
    
        return sequence[n - 1]; // Return the nth ugly number
    }
}

The provided Java solution implements an algorithm to find the nth ugly number. Ugly numbers are positive integers that only have prime factors of 2, 3, or 5.

Understanding the Code Structure:

• An array, sequence, stores the first n ugly numbers.
• Initialization: The first ugly number, 1, is directly assigned.
• Three pointers (multiple2Index, multiple3Index, multiple5Index) track the position in the ugly number sequence for multiplying by 2, 3, and 5, respectively.
• Variables next2, next3, and next5 represent the next potential ugly numbers from the respective sequences.

Key Steps in the Algorithm:

1. Iterate from 1 to n-1 to fill the sequence array:
   • Calculate the minimum of next2, next3, and next5 to determine the next ugly number.
   • Update the array with this minimum value.
   • Depending on which minimum value was chosen, increment the respective index and update the next variable by multiplying the new value from the sequence array by 2, 3, or 5.
2. Return the nth element of the sequence array, which is the nth ugly number.

This method efficiently calculates ugly numbers without multiplication of non-ugly numbers by maintaining three streams of potential candidates, reducing unnecessary computations.

class Solution:
    def getUglyNumber(self, count: int) -> int:
        sequence = [0] * count  
        sequence[0] = 1  
    
        idx2, idx3, idx5 = 0, 0, 0
        mult2, mult3, mult5 = 2, 3, 5
    
        for index in range(1, count):
            next_value = min(mult2, mult3, mult5)
            sequence[index] = next_value
    
            if next_value == mult2:
                idx2 += 1
                mult2 = sequence[idx2] * 2
            if next_value == mult3:
                idx3 += 1
                mult3 = sequence[idx3] * 3
            if next_value == mult5:
                idx5 += 1
                mult5 = sequence[idx5] * 5
    
        return sequence[count - 1]

The given code in Python provides a method to find the nth "ugly number". Ugly numbers are positive numbers whose only prime factors are 2, 3, or 5. Here's how this solution works:

• A class called Solution contains a method, getUglyNumber, which takes count, an integer that represents the position of the ugly number to find.

• The method initializes a list sequence of length count to store the sequence of ugly numbers, with the first element initialized to 1 since the first ugly number is 1.

• It sets three indices (idx2, idx3, idx5) to zero, which are used to track positions in the array for multiplication with 2, 3, and 5, respectively.

• Corresponding multiplication values (mult2, mult3, mult5) are initialized to 2, 3, and 5.

• A loop iterates through positions from the second position to the last in the sequence. At each position:

  • It finds the minimum of the multiplication values to determine the next ugly number.
  • This number is added to the sequence.
  • It then updates the indices and multipliers for future positions based on which base (2, 3, or 5) was used to generate the current ugly number.

• Finally, the nth ugly number (position count - 1 in the zero-indexed list) is returned.

This approach ensures the efficient calculation of ugly numbers using dynamic programming principles, particularly by maintaining a sequence and updating it based on previously found ugly numbers.