Thursday , September 21 2017
Home / C / Ugly Numbers Algorithm – C and Java Program

Ugly Numbers Algorithm – C and Java Program

C Program / Algorithm for Ugly Numbers:  What is an Ugly Number SeriesUgly Numbers are the ones whose prime factors are 2,3 or 5 Only. We have also given a Java Source code in Method #4

So Ugly Number Series is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, and so on…

The reason why 1 is added is because of the old convention and mostly 1 is added in many series may it be a Fibonacci series.

Ugly Numbers Source Code in C

  • Program #1

    # include<stdio.h>
    # include<stdlib.h>
     
    /*This function divides n1 by greatest divisible 
      power of n2*/
    int Primefact(int n1, int n2)
    {
      while (n1%n2 == 0)
       n1 = n1/n2; 
      return n1;
    }   
     
    /* Function to check if n1 number is ugly or not */
    int isUglyNumber(int num)
    {
      num = Primefact(num, 2);
      num = Primefact(num, 3);
      num = Primefact(num, 5);   
      return (num == 1)? 1 : 0;
    }    
     
    /* Function to get the nth ugly number*/
    int nthUglynum(int n)
    {
    int j = 1; 
    int count = 1;   /* a temporary variable to count Ugly Number*/ 
    /*To check all the numbers until n*/
      while (n > count)
      {
        j++;      
        if (isUglynum(j))
          count++;  // since i is ugly number thus count=count+1
      }
      return i;
    }
     
    int main()
    {
       int get;
        printf("Program for nth Ugly Number! Enter value of n");
    scanf("%d";&get);  
    printf("%d ugly number is= %d",nthuglynum(get));
        return 0;
    }
  • This approach has a time complexity of Big-O-Notation O(n).

    Splitting the Ugly number sequence of 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …into three groups –

    1. 1×2, 2×2, 3×2, 4×2, 5×2 . . .
    2. 1×3, 2×3, 3×3, 4×3, 5×3 . . .
    3. 1×5, 2×5, 3×5, 4×5, 5×5 . . .

    since each number can be divided by 2, 3, 5 only

    We can find that every sub sequence is the ugly-sequence itself (1, 2, 3, 4, 5, …) multiply 2, 3, 5. Then we use similar merge method as merge sort, to get every ugly number from the three subsequence. Every step we choose the smallest one, and move one step after.

    # include<stdio.h>
    # include<stdlib.h>
    # define bool int
     
    /* Function to find minimum of 3 numbers */
    int min(int , int , int );
     
    /* Function to get the nth ugly number*/
    int getNthUglyNo(int n)
    {
        int *ugly =
                 (int *)(malloc (sizeof(int)*n));
        int i2 = 0, i3 = 0, i5 = 0;
        int i;
        int n2= 2; // where n2= multiple of 2
        int n3= 3; // where n3=multiple of 3
        int n5= 5;//where n5=multiple of 5
        int next_uglynum = 1;
        *(ugly+0) = 1;
        for(i=1; i<n; i++)
        {
           next_uglynum = min(n2, n3,n5);
           *(ugly+i) = next_uglynum;                    
           if(next_uglynum == n2)
           {
               i2 = i2+1;       
               n2 = *(ugly+i2)*2;
           }
           if(next_uglynum == n3)
           {
               i3 = i3+1;
               n3 = *(ugly+i3)*3;
           }
           if(next_uglynum == n5)
           {
               i5 = i5+1;
               n5 = *(ugly+i5)*5;
           }
        } /*End of for loop (i=1; i<n; i++) */
        return next_uglynum;
    }
     
    /* Function to find minimum of 3 numbers */
    int min(int a, int b, int c)
    {
        if(a <= b)
        {
          if(a <= c)
            return a;
          else
            return c;
        }
        if(b <= c)
          return b;
        else
          return c;
    }
     
    /* Driver program to test above functions */
    int main()
    {
        int no = getNthUglyNo(150);
        printf("%dth ugly no. is %d ", 150, no);
        getchar();
        return 0;
    }

    Explanation:

    initializing the array
       ugly[] =  | 1 |
       i2 =  i3 = i5 = 0;
    
    First iteration
       ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
                = Min(2, 3, 5)
                = 2
       ugly[] =  | 1 | 2 |
       i2 = 1,  i3 = i5 = 0  (i2 is incremented ) 
    
    Second iteration
        ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
                 = Min(4, 3, 5)
                 = 3
        ugly[] =  | 1 | 2 | 3 |
        i2 = 1,  i3 =  1, i5 = 0  (i3 is incremented ) 
    
    Third iteration
        ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
                 = Min(4, 6, 5)
                 = 4
        ugly[] =  | 1 | 2 | 3 |  4 |
        i2 = 2,  i3 =  1, i5 = 0  (i2 is incremented )
    
    Fourth iteration
        ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
                  = Min(6, 6, 5)
                  = 5
        ugly[] =  | 1 | 2 | 3 |  4 | 5 |
        i2 = 2,  i3 =  1, i5 = 1  (i5 is incremented )
    
    Fifth iteration
        ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
                  = Min(6, 6, 10)
                  = 6
        ugly[] =  | 1 | 2 | 3 |  4 | 5 | 6 |
        i2 = 3,  i3 =  2, i5 = 1  (i2 and i3 is incremented )
    
    and so on.. to the value give by the user

     

    .

  • This is a trivial program.

      for (int a(2), uglyCount(0); ; a++) {
                if (a % 2 == 0)
                        continue;
                if (a % 3 == 0)
                        continue;
                if (a % 5 == 0)
                        continue;
                uglyCount++;
                if (uglyCount == n - 1)
                        break;
        }
  • Java Program: We have also listed a Ugly Number java Source code. This is a linear Solution of the Ugly Number series.

     int n = 1000;
    
        int last2 = 0;
        int last3 = 0;
        int last5 = 0;
    
        long[] ugly_no = new long[n];
        ugly_no[0] = 1;
        for (int i = 1; i < n; ++i) {
            long prev = ugly_no[i - 1];
    
            while (ugly_no[last2] * 2 <= prev) {
                ++last2;
            }
            while (ugly_no[last3] * 3 <= prev) {
                ++last3;
            }
            while (ugly_no[last5] * 5 <= prev) {
                ++last5;
            }
    
            long temp1 = ugly_no[last2] * 2;
            long temp2 = ugly_no[last3] * 3;
            long temp3 = ugly_no[last5] * 5;
    
            ugly_no[i] = Math.min(temp1, Math.min(temp2, temp3));
        }
    
        System.out.println(ugly_no[n - 1]);

     

Also see:

Ugly Number C Program

Ugly Number Java Program

Ugly Numbers Algo

Check Also

How to Solve Linear Equation in One Variable In C Programming?

C Program to Solve any Linear Equation in One Variable Find complete C program to ...

One comment

  1. 1 billionth ugly number:

    62565096724471903888424537973014890491686968126921250076541212862080934425144389
    76692222667734743108165348546009548371249535465997230641841310549077830079108427
    08520497989078343041081429889246063472775181069303596625038985214292236784430583
    66046734494015674435358781857279355148950650629382822451696203426871312216858487
    7816068576714140173718

Leave a Reply

Your email address will not be published. Required fields are marked *