Solution For Ugly Number Ii

Ugly Number II is a problem on Leetcode that requires us to find the nth ugly number. An ugly number is a number that only has 2, 3, or 5 as its prime factors.

Let’s start by defining a function nthUglyNumber(n) that takes in an integer n as its parameter and returns the nth ugly number. We will be using dynamic programming to solve this problem.

To solve this problem, we will be using three variables i2, i3, i5 to represent the index of the next ugly number that will be multiplied with 2, 3 and 5 respectively. We will also be using an array ugly to store the sequence of ugly numbers generated so far.

Here’s the algorithm:

1. Initialize the ugly array with the first ugly number 1.
2. Initialize i2, i3, and i5 to 0. These variables represent the index in the ugly array that will be multiplied with 2, 3 and 5 respectively.
3. For each ith number in the ugly array:
4. Compute the next possible ugly numbers by multiplying the current ugly numbers with 2, 3, and 5 respectively, that haven’t been added to the sequence yet.
5. Find the minimum value among the three possible numbers.
6. Add the minimum value to the ugly array.
7. Update i2, i3, and i5 based on which number was chosen.
8. Return the last element of the ugly array, which represents the nth ugly number.

Here’s the code:

“`
def nthUglyNumber(n):
ugly = [1] i2, i3, i5 = 0, 0, 0

while len(ugly) < n:
    # Compute the next possible ugly numbers
    next2 = ugly[i2] * 2
    next3 = ugly[i3] * 3
    next5 = ugly[i5] * 5

    # Find the minimum value among the three possible numbers
    next_ugly = min(next2, next3, next5)

    # Add the minimum value to the ugly array
    ugly.append(next_ugly)

    # Update i2, i3, and i5 based on which number was chosen
    if next_ugly == next2:
        i2 += 1
    if next_ugly == next3:
        i3 += 1
    if next_ugly == next5:
        i5 += 1

return ugly[-1]

“`

Time Complexity: O(n)

Space Complexity: O(n)

Step by Step Implementation For Ugly Number Ii

public class Solution {
    public int nthUglyNumber(int n) {
        if(n<=0) return 0;
        ArrayList list = new ArrayList();
        list.add(1);
        int i=0, j=0, k=0;
        while(list.size()
This is a Python 3 solution for the LeetCode problem "Ugly Number II":

def nthUglyNumber(n):

ugly_numbers = [1]

i2 = i3 = i5 = 0

while len(ugly_numbers) < n:

next_ugly = min(ugly_numbers[i2] * 2, ugly_numbers[i3] * 3, ugly_numbers[i5] * 5)

if next_ugly == ugly_numbers[i2] * 2:

i2 += 1

elif next_ugly == ugly_numbers[i3] * 3:

i3 += 1

else:

i5 += 1

ugly_numbers.append(next_ugly)

return ugly_numbers[-1]
var nthUglyNumber = function(n) {
    let ugly = [1];
    let i2 = 0, i3 = 0, i5 = 0;
    let next_multiple_of_2 = 2;
    let next_multiple_of_3 = 3;
    let next_multiple_of_5 = 5;
    let next_ugly_no = 1;
    for(let i = 1; i < n; i++) {
        next_ugly_no = Math.min(next_multiple_of_2, Math.min(next_multiple_of_3, next_multiple_of_5));
        ugly[i] = next_ugly_no;
        if(next_ugly_no == next_multiple_of_2) {
            i2 = i2+1;
            next_multiple_of_2 = ugly[i2]*2;
        }
        if(next_ugly_no == next_multiple_of_3) {
            i3 = i3+1;
            next_multiple_of_3 = ugly[i3]*3;
        }
        if(next_ugly_no == next_multiple_of_5) {
            i5 = i5+1;
            next_multiple_of_5 = ugly[i5]*5;
        }
    }
    return next_ugly_no;
};
class Solution {
public:
    int nthUglyNumber(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        int t2 = 0, t3 = 0, t5 = 0; //pointers for 2, 3, 5
        vector k(n);
        k[0] = 1;
        for(int i  = 1; i < n ; i ++)
        {
            k[i] = min(k[t2]*2,min(k[t3]*3,k[t5]*5));
            if(k[i] == k[t2]*2) t2++; 
            if(k[i] == k[t3]*3) t3++;
            if(k[i] == k[t5]*5) t5++;
        }
        return k[n-1];
    }
};
public class Solution {
    public int NthUglyNumber(int n) {
        //edge case
        if(n == 0){
            return 0;
        }
        //initialize list of ugly numbers and set 1 as the first ugly number
        List uglyNumbers = new List();
        uglyNumbers.Add(1);
        
        //initialize 3 pointers to keep track of the next ugly number to be added to the list
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        
        //loop through to find the nth ugly number
        while(uglyNumbers.Count < n){
            //find the next ugly number by finding the minimum of the product of the next 2, 3, and 5 pointer
            int nextUgly = Math.Min(Math.Min(2*uglyNumbers[i2], 3*uglyNumbers[i3]), 5*uglyNumbers[i5]);
            //add the next ugly number to the list
            uglyNumbers.Add(nextUgly);
            //if the minimum is the product of the next 2 pointer, increment the 2 pointer
            if(nextUgly == 2*uglyNumbers[i2]){
                i2++;
            }
            //if the minimum is the product of the next 3 pointer, increment the 3 pointer
            if(nextUgly == 3*uglyNumbers[i3]){
                i3++;
            }
            //if the minimum is the product of the next 5 pointer, increment the 5 pointer
            if(nextUgly == 5*uglyNumbers[i5]){
                i5++;
            }
        }
        //return the nth ugly number
        return uglyNumbers[n-1];
    }
}