Sort ugly numbers in an array at their relative positions | CPP implementation of the approach ; Function that returns true if n is an ugly number ; While divisible by 2 , keep dividing ; While divisible by 3 , keep dividing ; While divisible by 5 , keep dividing ; n must be 1 if it was ugly ; Function to sort ugly numbers in their relative positions ; To store the ugly numbers from the array ; If current element is an ugly number ; Add it to the ArrayList and set arr [ i ] to - 1 ; Sort the ugly numbers ; Position of an ugly number ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isUgly ( int n ) { while ( n % 2 == 0 ) n = n / 2 ; while ( n % 3 == 0 ) n = n / 3 ; while ( n % 5 == 0 ) n = n / 5 ; if ( n == 1 ) return true ; return false ; } void sortUglyNumbers ( int arr [ ] , int n ) { vector < int > list ; int i ; for ( i = 0 ; i < n ; i ++ ) { if ( isUgly ( arr [ i ] ) ) { list . push_back ( arr [ i ] ) ; arr [ i ] = -1 ; } } sort ( list . begin ( ) , list . end ( ) ) ; int j = 0 ; for ( i = 0 ; i < n ; i ++ ) { if ( arr [ i ] == -1 ) cout << list [ j ++ ] << " ▁ " ; else cout << arr [ i ] << " ▁ " ; } } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 7 , 12 , 10 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; sortUglyNumbers ( arr , n ) ; }