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 orderbool 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 vectorsort(v.begin(), v.end(), compare);// Print the vectorfor (int i = 0; i < v.size(); i++) cout << v[i].second << " ";}// Driver's Functionint 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 elementclass 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 STLfrom functools import cmp_to_key# creates the comparator for comparing first elementdef 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 Codearr = [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 elementfunction 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 Codeconst 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
