Sorting ugly numbers in an array at their relative positions in C++

Today, in this tutorial, we will get to know how to sort the ugly number present in an array of many numbers and some of which aren’t even ugly numbers, in C++. Ugly numbers are the numbers which have  2,3 or 5 as their only prime factors and not any other than these. Below you can see the source code of Sorting ugly numbers in an array at their relative positions in C++.

Number 1 is considered as an ugly number. Sequence of ugly number is 1,2,3,4,5,6,8,9,10,12,15…

Number 7,11 and 13 are excluded because they are prime numbers and 14 is excluded because 7 is the prime factor of 14.

Method to sort ugly numbers at their relative position 

Follow the steps::

  • Take input as array
  • Find the numbers which are ugly numbers and insert them into the vector by push_back function. Method to find if the number is an ugly number is as follows
    • First divide the number continuously by 2 till the remainder is 0.
    • Then divide the number continuously by 3 till the remainder is 0.
    • Then divide the number continuously by 5 till the remainder is 0.
    • If after these, the number remaining is 1 then it is an ugly number as that number does not have any other prime factor but if that number needs to be divided by some other prime factor to make it 1 then that number is not an ugly number.
  • Sort the vector by using the inbuilt “sort” function and print the array.

C++ program to sort ugly number at their relative position

Now we will see the C++ program to sort ugly numbers at their relative position in C++. Here first check whether the number is ugly or not. You can do this by continuously dividing it by 2,3 and 5 if the remainder is 0 till we get 1. If we get 1, the number is an ugly number else it is not. If the number is ugly, then push back or insert into the vector and after finding all the ugly numbers sort the vector using the inbuilt sort function.

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

int isNumberUgly(int i)
{
  while(i%2==0)
    i=i/2;
  while(i%3==0)
    i=i/3;
  while(i%5==0)
    i=i/5;
  if(i==1)
    return 1;
  else
    return 0;
}

int main()
{
  int size;
  cout << "Enter the size of array::" << endl;
  cin>>size;
  int array[size];
  vector <int> UglyNosArray;
  for(int i=0;i<size;i++)
  {
    cout<<"Element number"<<i+1<<"::";
    cin>>array[i];
  }
  int count=0;
  for(int i=0;i<size;i++)
  {
    if(isNumberUgly(array[i]))
    {
      UglyNosArray.push_back(array[i]);
      count++;
    }
  }

  sort(UglyNosArray.begin(),UglyNosArray.end());

  cout<<"\nSorted array of ugly numbers::"<<endl;
  for(int i=0;i<count;i++)
  {
    cout<<"Element number"<<i+1<<"::";
    cout<<UglyNosArray[i]<<endl;
  }

  return 0;
}

Output::

Enter the size of array::
5

Element number1::13
Element number1::9
Element number1::11
Element number1::3
Element number1::2

Sorted array::
Element number1::2
Element number2::3
Element number3::9

Also check:: C++ program to find the smallest prime divisor of a number

Leave a Reply

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