# Ugly Number II LeetCode Solution

Difficulty Level Medium

## Problem Statement

Ugly Number II LeetCode Solution – 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.

```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.```

## Explanation

We have an array k of the first n ugly number. We only know, in the beginning, the first one, which is 1. Then

k = min( kx2, kx3, kx5). The answer is kx2. So we move 2’s pointer to 1. Then we test:

k = min( kx2, kx3, kx5). And so on. Be careful about the cases such as 6, in which we need to forward both pointers of 2 and 3.

x here is multiplication.

## Approach

Let us solve this problem for the general case: that is not only for `2,3,5` divisors, but for any of them and any number of them. `factors = [2,3,5]` and `k=3` in our case.
Let `Numbers` be an array, where we keep all our ugly numbers. Also, note, that any ugly number is some other ugly number, multiplied by `2``3` or `5`. So, let `starts` be the indexes of ugly numbers, that when multiplied by `2``3` or `5` respectively, produces the smallest ugly number that is larger than the current overall maximum ugly number. Let us do several first steps to understand it better:

1. `starts = [0,0,0]` for numbers `2,3,5`, so `new_num = min(1*2,1*3,1*5) = 2`, and now `starts = [1,0,0]``Numbers = [1,2]`.
2. `starts = [1,0,0]`, so `new_num = min(2*2,1*3,1*5) = 3`, and now `starts = [1,1,0]``Numbers = [1,2,3]`.
3. `starts = [1,1,0]`, so `new_num = min(2*2,2*3,1*5) = 4`, so now `starts = [2,1,0]``Numbers = [1,2,3,4]`.
4. `starts = [2,1,0]`, so `new_num = min(3*2,2*3,1*5) = 5`, so now `starts = [2,1,1]``Numbers = [1,2,3,4,5]`.
5. `starts = [2,1,1]`, so `new_num = min(3*2,2*3,2*5) = 6`, so let us be careful in this case: we need to increase two numbers from `start`, because our new number `6` can be divided both by `2` and `3`, so now `starts = [3,2,1]``Numbers = [1,2,3,4,5,6]`.
6. `starts = [3,2,1]`, so `new_num = min(4*2,3*3,2*5) = 8`, so now `starts = [4,2,1]``Numbers = [1,2,3,4,5,6,8]`
7. `starts = [4,2,1]`, so `new_num = min(5*2,3*3,2*5) = 9`, so now `starts = [4,3,1]``Numbers = [1,2,3,4,5,6,8,9]`.
8. `starts = [4,3,1]`, so `new_num = min(5*2,4*3,2*5) = 10`, so we need to update two elements from `starts` and now `starts = [5,3,2]``Numbers = [1,2,3,4,5,6,8,9,10]`
9. `starts = [5,3,2]`, so `new_num = min(6*2,4*3,3*5) = 12`, we again need to update two elements from `starts`, and now `starts = [6,4,2]``Numbers = [1,2,3,4,5,6,8,9,10,12]`.
10. `starts = [6,4,2]`, so `new_num = min(8*2,5*3,3*5) = 15`, we again need to update two elements from `starts`, and now `starts = [6,5,3]``Numbers = [1,2,3,4,5,6,8,9,10,12,15]`.

## Code

### C++ Code For Ugly Number II

```class Solution {
public:
int nthUglyNumber(int n) {
if(n <= 0) return false; // get rid of corner cases
if(n == 1) return true; // base case
int t2 = 0, t3 = 0, t5 = 0; //pointers for 2, 3, 5
vector<int> k(n);
k = 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];
}
};```

### Java Code For Ugly Number II

```public class Solution {
public int nthUglyNumber(int n) {
int[] ugly = new int[n];
ugly = 1;
int index2 = 0, index3 = 0, index5 = 0;
int factor2 = 2, factor3 = 3, factor5 = 5;
for(int i=1;i<n;i++){
int min = Math.min(Math.min(factor2,factor3),factor5);
ugly[i] = min;
if(factor2 == min)
factor2 = 2*ugly[++index2];
if(factor3 == min)
factor3 = 3*ugly[++index3];
if(factor5 == min)
factor5 = 5*ugly[++index5];
}
return ugly[n-1];
}
}```

### Python Code For Ugly Number II

```class Solution:
def nthUglyNumber(self, n):
factors, k = [2,3,5], 3
starts, Numbers =  * k, 
for i in range(n-1):
candidates = [factors[i]*Numbers[starts[i]] for i in range(k)]
new_num = min(candidates)
Numbers.append(new_num)
starts = [starts[i] + (candidates[i] == new_num) for i in range(k)]
return Numbers[-1]```

## Complexity Analysis for Ugly Number II LeetCode Solution

O(N)

### Space Complexity

O(N)

Reference: https://en.wikipedia.org/wiki/Factor

Translate »