Ugly Numbers

November 25, 2021

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

Output 1

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[0] = 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 = 0, idx3 = 0, idx5 = 0;  // index of previous number
    ll next2 = 2, next3 = 3, next5 = 5; // What can be next multiple
    ll nextNo = 1; // next ugly number
 
    dp[0] = 1;
 
    for (ll i = 1; i < n; i++)
    {
        nextNo = min(next2, min(next3, next5));
        // 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

10
Nth ugly number is 12