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();
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();

//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
//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];
}
}```

Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]