# Ugly Number II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/ugly-number-ii)
Canonical: https://scaleengineer.com/dsa/problems/ugly-number-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Hash Table, Heap (Priority Queue)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [EPAM Systems](https://scaleengineer.com/companies/epam-systems)
---
## Problem
An **ugly number** is a positive integer whose prime factors are limited to `2`, `3`, and `5`.

Given an integer `n`, return _the_ `nth` _**ugly number**_.

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

**Constraints:**

* `1 <= n <= 1690`

# Approaches
## Brute Force Approach
Check each number starting from 1 and verify if it's an ugly number by dividing it by 2, 3, and 5 until we find the nth ugly number.
**Time:** O(n * log n) - We need to check n numbers and for each number, we perform divisions · **Space:** O(1) - Only using a constant amount of extra space
**Pros:** Simple to understand and implement; Works for small values of n; No extra space required except for variables
**Cons:** Very inefficient for large values of n; Checks many numbers that are not ugly; Performs redundant calculations
### Explanation
In this approach, we iterate through numbers starting from 1 and check if each number is an ugly number. A number is considered ugly if after dividing it by 2, 3, and 5 as many times as possible, we get 1.

```java
public int nthUglyNumber(int n) {
    int count = 1;
    int num = 1;
    
    while (count < n) {
        num++;
        if (isUgly(num)) {
            count++;
        }
    }
    return num;
}

private boolean isUgly(int num) {
    if (num <= 0) return false;
    
    while (num % 2 == 0) num /= 2;
    while (num % 3 == 0) num /= 3;
    while (num % 5 == 0) num /= 5;
    
    return num == 1;
}
```

This solution checks each number sequentially until it finds the nth ugly number. For each number, we check if it's ugly by continuously dividing by 2, 3, and 5 until we either get 1 (ugly number) or a number that's not divisible by any of these primes (not an ugly number).
### Algorithm
1. Initialize count = 1 and num = 1
2. While count < n:
   - Increment num
   - Check if num is ugly:
     * While num is divisible by 2, divide by 2
     * While num is divisible by 3, divide by 3
     * While num is divisible by 5, divide by 5
     * If final number is 1, it's ugly
   - If num is ugly, increment count
3. Return num

## Dynamic Programming with Three Pointers
Use dynamic programming to generate ugly numbers in order by maintaining three pointers for multiplying with 2, 3, and 5.
**Time:** O(n) - We only need to iterate through the array once · **Space:** O(n) - We need an array to store n ugly numbers
**Pros:** Generates ugly numbers in sequence without checking unnecessary numbers; Much more efficient than brute force approach; Each ugly number is calculated exactly once
**Cons:** Requires extra space to store all ugly numbers; May not be suitable for very large values of n due to memory constraints
### Explanation
This approach uses dynamic programming to generate ugly numbers in sequence. We maintain three pointers pointing to the previous numbers that need to be multiplied by 2, 3, and 5 respectively. At each step, we take the minimum of these three products to get the next ugly number.

```java
public int nthUglyNumber(int n) {
    int[] dp = new int[n];
    dp[0] = 1;
    
    int p2 = 0, p3 = 0, p5 = 0;
    
    for (int i = 1; i < n; i++) {
        int next2 = dp[p2] * 2;
        int next3 = dp[p3] * 3;
        int next5 = dp[p5] * 5;
        
        int nextUgly = Math.min(next2, Math.min(next3, next5));
        dp[i] = nextUgly;
        
        if (nextUgly == next2) p2++;
        if (nextUgly == next3) p3++;
        if (nextUgly == next5) p5++;
    }
    
    return dp[n-1];
}
```

The solution maintains an array dp where dp[i] represents the (i+1)th ugly number. We use three pointers p2, p3, and p5 to keep track of which previous ugly number should be multiplied by 2, 3, and 5 respectively. At each step, we take the minimum of these three products to get the next ugly number.
### Algorithm
1. Create dp array of size n and initialize dp[0] = 1
2. Initialize three pointers p2, p3, p5 = 0
3. For i from 1 to n-1:
   - Calculate next2 = dp[p2] * 2
   - Calculate next3 = dp[p3] * 3
   - Calculate next5 = dp[p5] * 5
   - Set dp[i] = min(next2, next3, next5)
   - Increment pointers corresponding to the minimum value used
4. Return dp[n-1]

# Solutions
### CSharp

```csharp
public class Solution {
    public int NthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; ++i) {
            int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
            dp[i] = Math.Min(next2, Math.Min(next3, next5));
            if (dp[i] == next2) {
                ++p2;
            }
            if (dp[i] == next3) {
                ++p3;
            }
            if (dp[i] == next5) {
                ++p5;
            }
        }
        return dp[n - 1];
    }
}
```

### Java

```java
import java.util.ArrayList ; import java.util.List ; public class Ugly_Number_II { public static void main ( String [] args ) { Ugly_Number_II out = new Ugly_Number_II (); Solution s = out . new Solution (); System . out . println ( s . nthUglyNumber ( 10 )); } public class Solution { public int nthUglyNumber ( int n ) { if ( n <= 0 ) { return 0 ; } List < Integer > nums = new ArrayList <>(); nums . add ( 1 ); int i2 = 0 ; int i3 = 0 ; int i5 = 0 ; while ( nums . size () < n ) { int m2 = nums . get ( i2 ) * 2 ; int m3 = nums . get ( i3 ) * 3 ; int m5 = nums . get ( i5 ) * 5 ; int mn = Math . min ( Math . min ( m2 , m3 ), m5 ); nums . add ( mn ); if ( mn == m2 ) { i2 ++; } if ( mn == m3 ) { // @note: 3*2 and 2*3 are both 6, so cannot else-if i3 ++; } if ( mn == m5 ) { i5 ++; } } return nums . get ( nums . size () - 1 ); } } } ############ class Solution { public int nthUglyNumber ( int n ) { int [] dp = new int [ n ]; dp [ 0 ] = 1 ; int p2 = 0 , p3 = 0 , p5 = 0 ; for ( int i = 1 ; i < n ; ++ i ) { int next2 = dp [ p2 ] * 2 , next3 = dp [ p3 ] * 3 , next5 = dp [ p5 ] * 5 ; dp [ i ] = Math . min ( next2 , Math . min ( next3 , next5 )); if ( dp [ i ] == next2 ) ++ p2 ; if ( dp [ i ] == next3 ) ++ p3 ; if ( dp [ i ] == next5 ) ++ p5 ; } return dp [ n - 1 ]; } }
```

### JavaScript

```javascript
/** * @param {number} n * @return {number} */ var nthUglyNumber = function (n) {
  let dp = [1];
  let p2 = 0,
    p3 = 0,
    p5 = 0;
  for (let i = 1; i < n; ++i) {
    const next2 = dp[p2] * 2,
      next3 = dp[p3] * 3,
      next5 = dp[p5] * 5;
    dp[i] = Math.min(next2, Math.min(next3, next5));
    if (dp[i] == next2) ++p2;
    if (dp[i] == next3) ++p3;
    if (dp[i] == next5) ++p5;
    dp.push(dp[i]);
  }
  return dp[n - 1];
};

```

### Python

```python
class Solution : def nthUglyNumber ( self , n : int ) -> int : if n <= 0 : return 0 nums = [ 1 ] i2 , i3 , i5 = 0 , 0 , 0 while len ( nums ) < n : m2 = nums [ i2 ] * 2 m3 = nums [ i3 ] * 3 m5 = nums [ i5 ] * 5 mn = min ( m2 , m3 , m5 ) nums . append ( mn ) if mn == m2 : i2 += 1 if mn == m3 : # Note: 3*2 and 2*3 are both 6, so cannot use elif i3 += 1 if mn == m5 : i5 += 1 return nums [ - 1 ] ############ from heapq import heappop class Solution : def nthUglyNumber ( self , n : int ) -> int : h = [ 1 ] # heap vis = { 1 } # hashtable to de-dup ans = 1 for _ in range ( n ): ans = heappop ( h ) for v in [ 2 , 3 , 5 ]: nxt = ans * v if nxt not in vis : vis . add ( nxt ) heappush ( h , nxt ) return ans ############ class Solution : def nthUglyNumber ( self , n : int ) -> int : dp = [ 1 ] * n p2 = p3 = p5 = 0 for i in range ( 1 , n ): next2 , next3 , next5 = dp [ p2 ] * 2 , dp [ p3 ] * 3 , dp [ p5 ] * 5 dp [ i ] = min ( next2 , next3 , next5 ) if dp [ i ] == next2 : p2 += 1 if dp [ i ] == next3 : p3 += 1 if dp [ i ] == next5 : p5 += 1 return dp [ n - 1 ] ############ class Solution ( object ): def nthUglyNumber ( self , n ): """ :type n: int :rtype: int """ dp = [ 0 ] * ( n + 1 ) dp [ 1 ] = 1 i2 = i3 = i5 = 1 for i in range ( 2 , n + 1 ): dp [ i ] = min ( dp [ i2 ] * 2 , dp [ i3 ] * 3 , dp [ i5 ] * 5 ) if dp [ i ] == dp [ i2 ] * 2 : i2 += 1 if dp [ i ] == dp [ i3 ] * 3 : i3 += 1 if dp [ i ] == dp [ i5 ] * 5 : i5 += 1 return dp [ - 1 ]
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/ugly-number-ii/ // Time: O(N) // Space: O(N) class Solution { public: int nthUglyNumber ( int n ) { vector < int > num ( n ); num [ 0 ] = 1 ; int i = 0 , j = 0 , k = 0 ; for ( int t = 1 ; t < n ; ++ t ) { num [ t ] = min ({ num [ i ] * 2 , num [ j ] * 3 , num [ k ] * 5 }); if ( num [ t ] == num [ i ] * 2 ) ++ i ; if ( num [ t ] == num [ j ] * 3 ) ++ j ; if ( num [ t ] == num [ k ] * 5 ) ++ k ; } return num . back (); } };
```