text: # Ugly Numbers
  
  Difficulty Level Easy
  Frequently asked in Delhivery Goldman Sachs Paytm
  MathViews 1795
  
  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.
  
  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 nthUgly 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 nthUgly 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 0th 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 nthUgly 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 nthUgly 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`
  Translate »