# Ugly Numbers

## Ugly Numbers

Ugly Numbers is a famous problem asked in many coding interviews and coding rounds. In this article we will be explaining dynamic programming solution with C++ code of this problem. ## Ugly Numbers Problem Description

An ugly number is a number whose prime factors are only 2, 3 & 5. In other words, a number X must be of form X = 2^a * 3^b * 5^c. Given an integer n, return nth ugly number.

Input:

• Single line input containing an integer n.

Output:

• The required number.

Example

Input 1

• 5

Output 1

• 5

Explanation

• The First 5 ugly numbers are : 1, 2, 3, 4 & 5.

## Ugly Numbers Problem Solution

• We know the first ugly number is 1.
• We create a dp array to where dp[n-1] = nth ugly number (0 based indexing). This means dp = 1;
• Now we know nth ugly number will be minimum of all previous numbers multiplied by 2,3 or 5 & the number should be greater than previous ugly number. If we find this iteratively, this would make our solution O(n^2).
• To further reduce the time complexity to O(n) we keep track of minimum next multiples of 2, 3 & 5 and corresponding minimum indicies of dp array. We then use these to find next number. Refer to code below for more details.

Time Complexity – O(n)

Space Complexity – O(n)

### Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll uglyNumber(ll n)
{
ll dp[n]; // Stores the nth ugly number (0 based indexing)

ll idx2 = 0idx3 = 0idx5 = 0;  // index of previous number
ll next2 = 2next3 = 3next5 = 5; // What can be next multiple
ll nextNo = 1; // next ugly number

dp = 1;

for (ll i = 1i < ni++)
{
nextNo = min(next2min(next3next5));
// Next ugly number is minimum of all next2,next3,next5
dp[i] = nextNo;
// Updating next2
if (nextNo == next2)
{
idx2++;
next2 = dp[idx2] * 2;
}
// Updating next3
if (nextNo == next3)
{
idx3++;
next3 = dp[idx3] * 3;
}
// Updating next5
if (nextNo == next5)
{
idx5++;
next5 = dp[idx5] * 5;
}
}

return dp[n – 1];
}
int main()
{
ll n;
cin >> n;
cout<<“Nth ugly number is “<<uglyNumber(n)<<endl;
return 0;
}

### Output

`10Nth ugly number is 12`