# Sort elements on the basis of number of factors

• Difficulty Level : Easy
• Last Updated : 02 Jun, 2022

Given an array of positive integers. Sort the given array in decreasing order of number of factors of each element, i.e., element having the highest number of factors should be the first to be displayed and the number having least number of factors should be the last one. Two elements with equal number of factors should be in the same order as in the original array.
Examples:

```Input : {5, 11, 10, 20, 9, 16, 23}
Output : 20 16 10 9 5 11 23
Number of distinct factors:
For 20 = 6, 16 = 5, 10 = 4, 9 = 3
and for 5, 11, 23 = 2 (same number of factors
therefore sorted in increasing order of index)

Input : {104, 210, 315, 166, 441, 180}
Output : 180 210 315 441 104 166```

The following steps sort numbers in decreasing order of count of factors.

1. Count distinct number of factors of each element. Refer this.
2. You can use a structure for each element to store its original index and count of factors. Create an array of such structures to store such information for all the elements.
3. Sort this array of structures on the basis of the problem statement using any sorting algorithm.
4. Traverse this array of structures from the beginning and get the number from the original array with the help of the index stored in the structure of each element of the sorted array of structures.

## C++

 `// C++ implementation to sort numbers on``// the basis of factors``#include ` `using` `namespace` `std;` `// structure of each element having its index``// in the input array and number of factors``struct` `element``{``    ``int` `index, no_of_fact;``};` `// function to count factors for``// a given number n``int` `countFactors(``int` `n)``{``    ``int` `count = 0;``    ``int` `sq = ``sqrt``(n);``    ` `    ``// if the number is a perfect square``    ``if` `(sq * sq == n)``        ``count++;``    ` `    ``// count all other factors``    ``for` `(``int` `i=1; i<``sqrt``(n); i++)``    ``{``        ``// if i is a factor then n/i will be``        ``// another factor. So increment by 2``        ``if` `(n % i == 0)   ``            ``count += 2;``    ``}       ``    ` `    ``return` `count;``}` `// comparison function for the elements``// of the structure``bool` `compare(``struct` `element e1, ``struct` `element e2)``{``    ``// if two elements have the same number``    ``// of factors then sort them in increasing``    ``// order of their index in the input array``    ``if` `(e1.no_of_fact == e2.no_of_fact)``        ``return` `e1.index < e2.index;``    ` `    ``// sort in decreasing order of number of factors``    ``return` `e1.no_of_fact > e2.no_of_fact;   ``}` `// function to print numbers after sorting them in``// decreasing order of number of factors``void` `printOnBasisOfFactors(``int` `arr[], ``int` `n)``{   ``    ``struct` `element num[n];``    ` `    ``// for each element of input array create a``    ``// structure element to store its index and``    ``// factors count``    ``for` `(``int` `i=0; i

## Java

 `// Java implementation to sort numbers on``// the basis of factors` `import` `java.util.Arrays;``import` `java.util.Comparator;` `class` `Element``{``    ``//each element having its index``    ``// in the input array and number of factors``    ``int` `index, no_of_fact;`` ` `    ``public` `Element(``int` `i, ``int` `countFactors)``    ``{``        ``index = i;``        ``no_of_fact = countFactors;``    ``}` `    ``// method to count factors for``    ``// a given number n``    ``static` `int` `countFactors(``int` `n)``    ``{``        ``int` `count = ``0``;``        ``int` `sq = (``int``)Math.sqrt(n);``     ` `        ``// if the number is a perfect square``        ``if` `(sq * sq == n)``            ``count++;``     ` `        ``// count all other factors``        ``for` `(``int` `i=``1``; i() {` `            ``@Override``            ``// compare method for the elements``            ``// of the structure``            ``public` `int` `compare(Element e1, Element e2) {``                ``// if two elements have the same number``                ``// of factors then sort them in increasing``                ``// order of their index in the input array``                ``if` `(e1.no_of_fact == e2.no_of_fact)``                 ``return` `e1.index < e2.index ? -``1` `: ``1``;``              ` `                ``// sort in decreasing order of number of factors``                ``return` `e1.no_of_fact > e2.no_of_fact ? -``1` `: ``1``; ``            ``}``            ` `        ``});``     ` `        ``// access index from the structure element and corresponding``        ``// to that index access the element from arr``        ``for` `(``int` `i=``0``; i

## Javascript

 ``

Output:

`20 16 10 9 5 11 23`

Time Complexity: O(n √n)
This article is contributed by Ayush Jauhari. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.