Sort elements on the basis of number of factors | C ++ implementation to sort numbers on the basis of factors ; structure of each element having its index in the input array and number of factors ; function to count factors for a given number n ; if the number is a perfect square ; count all other factors ; if i is a factor then n / i will be another factor . So increment by 2 ; comparison function for the elements of the structure ; if two elements have the same number of factors then sort them in increasing order of their index in the input array ; sort in decreasing order of number of factors ; function to print numbers after sorting them in decreasing order of number of factors ; for each element of input array create a structure element to store its index and factors count ; sort the array of structures as defined ; access index from the structure element and corresponding to that index access the element from arr ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct element { int index , no_of_fact ; } ; int countFactors ( int n ) { int count = 0 ; int sq = sqrt ( n ) ; if ( sq * sq == n ) count ++ ; for ( int i = 1 ; i < sqrt ( n ) ; i ++ ) { if ( n % i == 0 ) count += 2 ; } return count ; } bool compare ( struct element e1 , struct element e2 ) { if ( e1 . no_of_fact == e2 . no_of_fact ) return e1 . index < e2 . index ; return e1 . no_of_fact > e2 . no_of_fact ; } void printOnBasisOfFactors ( int arr [ ] , int n ) { struct element num [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { num [ i ] . index = i ; num [ i ] . no_of_fact = countFactors ( arr [ i ] ) ; } sort ( num , num + n , compare ) ; for ( int i = 0 ; i < n ; i ++ ) cout << arr [ num [ i ] . index ] << " ▁ " ; } int main ( ) { int arr [ ] = { 5 , 11 , 10 , 20 , 9 , 16 , 23 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printOnBasisOfFactors ( arr , n ) ; return 0 ; }