Ugly Numbers

The positive numbers whose only prime factors are 2, 3, or 5 are known as ugly numbers. For eg- 8 is an ugly number because it’s an only prime factor is 2 but 7 is not an ugly number because it’s a prime factor is 7. 1 being an exception is included.

Given an integer n. Find the n^th Ugly Number

Example

Input: 25

Output: 54

Input: 36

Output: 120

Iterative Method for Ugly Numbers

Algorithm for Ugly Numbers

1.  Initialize a variable count=1 to count the ugly numbers.
2.  Iterate over a variable i=1.
3.  Increment i by 1.
4.  Divide it by the greatest divisible powers of 2,3 and 5 and return the result.
5.  If the value of the result is 1 that is i is completely divisible by 2,3 or 5, increment the count.
6.  Repeat steps 3,4 and 5 until count=n.
7.  Return i.

Time Complexity: O(nlogn)

Space Complexity: O(1)

C++ Program to find n^th Ugly Number

#include <bits/stdc++.h>
using namespace std;

/* Function to divide the integer by 
    greatest divisible powers of 2,3,5 */
int Div(int x, int y){ 
    while(x%y==0){ 
        x=x/y;  
    } 
    return x; 
}     
/* Function to get the ugly 
    number*/
int uglyNo(int n){ 
    int i=1;  
    int count=1;  
    
    while(n>count){ 
        i++;
        int p=i;
        p=Div(p,2); 
        p=Div(p,3); 
        p=Div(p,5); 
        if(p==1){ 
            count++;
        }  
    } 
    return i; 
} 
int main(){
    int n=9;
    cout<<uglyNo(n);
    return 0;
}

Output : 10

Java Program to find n^th Ugly Number

class Ugly{ 
    /* Function to divide the integer by 
        greatest divisible powers of 2,3,5 */
    static int Div(int x,int y){ 
        while(x%y==0) 
            x=x/y; 
        return x; 
    } 
    /* Function to get the ugly 
       number*/
    static int uglyNo(int n){ 
        int i=1; 
        int count=1;  
        while(n>count){ 
            i++; 
            int p=i;
            p=Div(p,2); 
            p=Div(p,3); 
            p=Div(p,5); 
            if(p==1){ 
                count++;
            }
        } 
        return i; 
    } 
    public static void main(String args[]){ 
        int n=9;
        int num = uglyNo(n); 
        System.out.println(num); 
    } 
} 

Output : 10

Dynamic Programming Method for Ugly Numbers

In this method, only those numbers that are multiples of 2,3 and 5 are considered.

For eg- 2×1, 2×2, 2×3…….

            3×1, 3×2, 3×3…….

            5×1, 5×2, 5×3…….

The minimum ugly number is selected from these sequences at each step and the pointer increments by 1.

Algorithm

1.  Initialize three-pointers two, three, and five pointing to zero.
2.  Take 3 variables nm2, nm3, and nm5 to keep track of next multiple of 2,3 and 5.
3.  Make an array of size n to store the ugly numbers with 1 at 0^th index.
4.  Initialize a variable next which stores the value of the last element in the array.
5.  Run a loop n-1 times and perform steps 6,7 and 8.
6.  Update the values of nm2, nm3, nm5 as ugly[two]*2, ugly[three]*3, ugly[5]*5 respectively.
7.  Select the minimum value from nm2, nm3, and nm5 and increment the pointer related to it.           
8.  Store the minimum value in variable next and array.
9.  Return next.

Explanation

Let n = 4

two=0, three=0, five=0, next=1

ugly[n] = | 1 |, nm2=2, nm3=3, nm5=5

first iteration

next = min(nm2, min(nm3, nm5))  = min(2, min(3, 5)) =2

ugly[1] = 2, two=1 , nm2 = ugly[two]x2 = ugly[1]x2 = 2×2 =4

ugly[n] = | 1 | 2 |

next = 2

second iteration

next = min(nm2, min(nm3, nm5))  = min(4, min(3, 5)) =3

ugly[2] = 3, three=1 , nm3 = ugly[three]x3 = ugly[1]x3 = 3×3 =9

ugly[n] = | 1 | 2 | 3 |

next = 3

third iteration

next = min(nm2, min(nm3, nm5))  = min(4, min(9, 5)) =4

ugly[3] = 4, two=2 , nm2 = ugly[two]x2 = ugly[2]x2 = 3×2 =6

After n-1 that is 3 iterations-

ugly[n] = | 1 | 2 | 3 | 4 |

next = 4     // The fourth ugly number is four

Time Complexity: O(n)

Space Complexity: O(n)

C++ Program to find n^th Ugly Number

#include<bits/stdc++.h> 
using namespace std; 

/* Function to get the nth ugly number*/
int uglyNo(int n){ 
    int ugly[n], two=0, three=0, five=0; 
    int nm2=2, nm3=3, nm5=5, next=1; 
    
    ugly[0] = 1; 
    for (int i=1; i<n; i++){ 
        next = min(nm2,min(nm3,nm5));
        ugly[i] = next; 
        if(next==nm2){ 
            two++; 
            nm2 = ugly[two]*2; 
        } 
        if(next==nm3){ 
            three++; 
            nm3 = ugly[three]*3; 
        }  
        if(next==nm5){ 
            five++; 
            nm5 = ugly[five]*5; 
        }  
    }
    return next; 
} 
int main(){ 
    int n=9; 
    cout<<uglyNo(n); 
    return 0; 
}

Output : 10

Java Program to find n^th Ugly Number

import java.lang.Math; 
  
class Ugly{ 
    /* Function to get the nth ugly number*/
    int uglyNo(int n){ 
        int ugly[] = new int[n];
        int two=0, three=0, five=0; 
        int nm2=2, nm3=3, nm5=5, next=1; 
        
        ugly[0] = 1; 
        
        for(int i=1; i<n; i++){ 
            next = Math.min(nm2, Math.min(nm3, nm5)); 
              
            ugly[i] = next; 
            if(next == nm2){ 
               two = two+1; 
               nm2 = ugly[two]*2; 
            } 
            if(next == nm3){ 
               three = three+1; 
               nm3 = ugly[three]*3; 
            } 
            if(next == nm5){ 
               five = five+1; 
               nm5 = ugly[five]*5; 
            } 
        }
        return next; 
    } 
    public static void main(String args[]){ 
        int n = 9; 
        Ugly obj = new Ugly(); 
        System.out.println(obj.uglyNo(n)); 
    } 
} 

Output : 10

Reference Interview Questions