Data Modelling & AI Data Structure & Algorithm

Sort on the basis of number of factors using STL

23 June 2025

0

Given an array of positive integers. Sort the given array in decreasing order of a number of factors of each element, i.e., an element having the highest number of factors should be the first to be displayed and the number having the least number of factors should be the last one. Two elements with an 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

We have already discussed a structure-based solution to sort according to a number of factors. The following steps sort numbers in decreasing order of count of factors.

Count a distinct number of factors of each element. Refer this.
Create a vector of pairs that stores elements and their factor counts.
Sort this array based on the problem statement using any sorting algorithm.

Implementation:

CPP

// Sort an array of numbers according
// to number of factors.
#include <bits/stdc++.h>
using namespace std;
 
// Function that helps to sort elements 
// in descending order
bool compare(const pair<int, int> &a,
            const pair<int, int> &b) {
return (a.first > b.first);
}
 
// Prints array elements sorted in descending
// order of number of factors.
void printSorted(int arr[], int n) {
 
vector<pair<int, int>> v;
 
for (int i = 0; i < n; i++) {
 
    // Count factors of arr[i].
    int count = 0;
    for (int j = 1; j * j <= arr[i]; j++) {
 
    // To check Given Number is Exactly
    // divisible
    if (arr[i] % j == 0) {
        count++;
 
        // To check Given number is perfect
        // square
        if (arr[i] / j != j)
        count++;
    }
    }
 
    // Insert factor count and array element
    v.push_back(make_pair(count, arr[i]));
}
 
// Sort the vector
sort(v.begin(), v.end(), compare);
 
// Print the vector
for (int i = 0; i < v.size(); i++) 
    cout << v[i].second << " ";
}
 
// Driver's Function
int main() {
int arr[] = {5, 11, 10, 20, 9, 16, 23};
int n = sizeof(arr) / sizeof(arr[0]);
 
printSorted(arr, n);
 
return 0;
}

Java

// java program to Sort on the basis of 
// number of factors using STL
  
import java.io.*;
import java.util.*;  
 
class Pair
{
    int a;
    int b;
    Pair(int a, int b)
    {
        this.a=a;
        this.b=b;
         
    }
     
}
 
// creates the comparator for comparing first element
class SComparator implements Comparator<Pair> {
    // override the compare() method
    public int compare(Pair o1, Pair o2)
    {
        if (o1.a == o2.a) {
            return 0;
        }
        else if (o1.a < o2.a) {
            return 1;
        }
        else {
            return -1;
        }
    }
}
 
class GFG {
    // Function to find maximum partitions.
    static void printSorted(int arr[], int n)
    {
        ArrayList<Pair> v = new ArrayList<Pair>();
         for (int i = 0; i < n; i++) {
   
        // Count factors of arr[i].
        int count = 0;
        for (int j = 1; j * j <= arr[i]; j++) {
       
          // To check Given Number is Exactly
          // divisible
          if (arr[i] % j == 0) {
            count++;
       
            // To check Given number is perfect
            // square
            if (arr[i] / j != j)
              count++;
          }
    }
   
    // Insert factor count and array element
    v.add(new Pair (count, arr[i]));
  }
   
  // Sort the vector
  // Sorting the arraylist elements in descending order
    Collections.sort(v, new SComparator());
   
  // Print the vector
  for (Pair i : v) 
    System.out.print(i.b+" ");
}
  
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 5, 11, 10, 20, 9, 16, 23 };
        int n = arr.length;
        printSorted(arr, n);
    }
}
  
// This code is contributed by Aarti_Rathi

Python3

# python program to Sort on the basis of
# number of factors using STL
from functools import cmp_to_key
 
# creates the comparator for comparing first element
def compare(a, b):
    return b[0] - a[0]
     
# Function to find maximum partitions.
def printSorted(arr,n):
    v =[]
    for i in range(n):
        count=0
        j=1
        # Count factors of arr[i].
        while(j*j<=arr[i]):
             
            # To check Given Number is Exactly
            # divisible
            if(arr[i]%j ==0):
                count+=1
                 
                # To check Given number is perfect
                # square
                if(arr[i]/j!=j):
                    count+=1
                 
            j+=1
        # Insert factor count and array element
        v.append((count,arr[i]))
         
    # Sort the vector
    # Sorting the arraylist elements in descending order 
    v=sorted(v, key=cmp_to_key(compare))
     
    # Print the vector
    for a,b in v:
        print(b,end=" ")
 
# Driver Code
arr = [5, 11, 10, 20, 9, 16, 23]
n = len(arr)
printSorted(arr, n)
 
# This code is contributed by Aarti_Rathi

C#

// C# program to Sort on the basis of 
// number of factors using STL 
 
using System; 
using System.Collections.Generic; 
 
// Class Pair 
class Pair 
{ 
    public int a; 
    public int b; 
    public Pair(int a, int b) 
    { 
        this.a = a; 
        this.b = b; 
         
    } 
     
} 
 
// creates the comparator for comparing first element 
class SComparator : IComparer<Pair> 
{ 
    // override the compare() method 
    public int Compare(Pair o1, Pair o2) 
    { 
        if (o1.a == o2.a) 
        { 
            return 0; 
        } 
        else if (o1.a < o2.a) 
        { 
            return 1; 
        } 
        else
        { 
            return -1; 
        } 
    } 
} 
public class GFG{
    // Function to find maximum partitions. 
    static void printSorted(int[] arr, int n) 
    { 
        List<Pair> v = new List<Pair>(); 
         for (int i = 0; i < n; i++) 
        { 
     
            // Count factors of arr[i]. 
            int count = 0; 
            for (int j = 1; j * j <= arr[i]; j++) 
            { 
         
                // To check Given Number is Exactly 
                // divisible 
                if (arr[i] % j == 0) 
                { 
                    count++; 
         
                    // To check Given number is perfect 
                    // square 
                    if (arr[i] / j != j) 
                        count++; 
                } 
            } 
         
            // Insert factor count and array element 
            v.Add(new Pair (count, arr[i])); 
        } 
         
        // Sort the vector 
        // Sorting the list elements in descending order 
        v.Sort(new SComparator()); 
         
        // Print the vector 
        foreach (Pair i in v) 
            Console.Write(i.b + " "); 
    } 
     
    // Driver code 
        static public void Main (){
        int[] arr = { 5, 11, 10, 20, 9, 16, 23 }; 
        int n = arr.Length; 
        printSorted(arr, n); 
    } 
} 
 
// This code is contributed by akashish__

Javascript

// creates the comparator for comparing first element
function compare(a, b) {
  return b[0] - a[0];
}
 
// Function to find maximum partitions.
function printSorted(arr) {
  const n = arr.length;
  const v = [];
  for (let i = 0; i < n; i++) {
    let count = 0;
    let j = 1;
     
    // Count factors of arr[i].
    while (j * j <= arr[i])
    {
     
      // To check Given Number is Exactly divisible
      if (arr[i] % j == 0) {
        count++;
         
        // To check Given number is perfect square
        if (arr[i] / j != j) count++;
      }
      j++;
    }
     
    // Insert factor count and array element
    v.push([count, arr[i]]);
  }
   
  // Sort the vector
  // Sorting the arraylist elements in descending order
  v.sort(compare);
   
  // Print the vector
  v.forEach((i) => console.log(i[1]));
}
 
// Driver Code
const arr = [5, 11, 10, 20, 9, 16, 23];
printSorted(arr);
 
// This code is contributed by Shivhack999

Output:

20 16 10 9 5 11 23

Time Complexity: O(n*log(n))
Auxiliary Complexity: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

1 COMMENT

spielplatz im freien 7 June 2026 At 2:56 am

… [Trackback]

[…] Read More on to that Topic: geeksforgeeks.org/sort-on-the-basis-of-number-of-factors-using-stl/ […]

Log in to leave a comment

Sort on the basis of number of factors using STL

CPP

Java

Python3

C#

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

1 COMMENT

LEAVE A REPLY Cancel reply

Most Popular

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

Your Galaxy S25 just picked up three more Galaxy AI features

No one can agree on these phones. [Video]

EDITOR PICKS

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

Your Galaxy S25 just picked up three more Galaxy AI features

POPULAR POSTS

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

Your Galaxy S25 just picked up three more Galaxy AI features

POPULAR CATEGORY

ABOUT US

FOLLOW US