Given an array arr[] consisting of N positive integers, the task is to sort the array arr[] according to the increasing order of GCD of digits of each element. If GCD of two or more elements are the same then, sort according to their values.
Examples:
Input: arr[] = {555, 363, 488, 244}
Output: 244 363 488 555
Explanation:
Following the GCD of the digits of each number:
- 555: GCD(5, 5, 5) = 5.
- 363: GCD(3, 6, 3) = 3.
- 488: GCD(4, 8, 8) = 4.
- 244: GCD(2, 4, 4) = 2.
After sorting according the given criteria, the order of elements are {244, 363, 488, 555}.
Input: arr[] = {555, 363, 488, 244, 444, 5}
Output: 244 363 444 488 5 555
Approach: The given problem can be solved by using the comparator function with the sort() function. The comparator function is defined as:
- It takes two arguments at a time and returns true if the GCD of the first argument is less than the second argument.
- If the GCD value is the same, then it returns true if the first argument is less than the second argument. Otherwise, return false.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include<bits/stdc++.h>using namespace std;// Function to calculate GCD of two integersint gcd(int a, int b){ // Base case if (b == 0) return a; // Recursively calculate GCD return gcd(b, a % b);} // Function to calculate GCD of// digits of array elementsint keyFunc(int n){ int getGCD = 0; while (n > 0) { getGCD = gcd(n % 10, getGCD); // If at point GCD becomes 1, // return it if (getGCD == 1) return 1; n = n / 10; } return getGCD;}// Comparator function that compares // elements according to their gcd value.bool compare(int o1, int o2){ int x = keyFunc(o1); int y = keyFunc(o2); if(x == y) { return o1 < o2; } return x < y;} // Function to sort an array in according// to GCD of digits of array elementsvoid sortArrayByGCD(vector<int>arr){ vector<int>list; for(int i : arr) { list.push_back(i); } // Sort the array according to gcd of // digits using comparator function sort(list.begin(), list.end(), compare); // Print the resultant array for(int i : list) { cout << i << " "; }} // Driver codeint main(){ vector<int>arr = { 555, 363, 488, 244 };; sortArrayByGCD(arr);}// This code is contributed by nirajgusain5 |
Java
// Java program for the above approachimport java.util.ArrayList;import java.util.Collections;import java.util.Comparator;class GFG{ // Function to calculate GCD of two integersstatic int gcd(int a, int b){ // Base case if (b == 0) return a; // Recursively calculate GCD return gcd(b, a % b);}// Function to calculate GCD of // digits of array elementsstatic int keyFunc(int n){ int getGCD = 0; while (n > 0) { getGCD = gcd(n % 10, getGCD); // If at point GCD becomes 1, // return it if (getGCD == 1) return 1; n = n / 10; } return getGCD;}// Function to sort an array in according // to GCD of digits of array elementspublic static void sortArrayByGCD(int[] arr){ ArrayList<Integer> list = new ArrayList<Integer>(); for(int i : arr) { list.add(i); } // Sort the array according to gcd of // digits using comparator function Collections.sort(list, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { int x = keyFunc(o1) - keyFunc(o2); if (x == 0) { if (o1 > o2) x = 1; else x = -1; } return x; } }); // Print the resultant array for(int i : list) { System.out.print(i + " "); }}// Driver codepublic static void main(String[] args){ int arr[] = { 555, 363, 488, 244 }; sortArrayByGCD(arr);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach# Function to calculate# GCD of two integersdef gcd(a, b): # Base Case if not b: return a # Recursively calculate GCD return gcd(b, a % b)# Function to calculate GCD# of two array elementsdef keyFunc(n): getGCD = int(str(n)[0]) # Update the getGCD for i in str(n): getGCD = gcd(getGCD, int(i)) # Return the resultant GCD return getGCD# Function to sort an array by# increasing order of GCD of# digits of array elementsdef sortArrayByGCD(arr): # Sort the array arr.sort() # Sort the array according to gcd of # digits using comparator function arr = sorted(arr, key = keyFunc) # Print the resultant array print(*arr)# Driver Code # Given arrayarr = [555, 363, 488, 244]sortArrayByGCD(arr) |
C#
using System;using System.Linq;class GFG{ static int Gcd(int a, int b) { if (b == 0) return a; return Gcd(b, a % b); } static int KeyFunc(int n) { int gcd = 0; while (n > 0) { gcd = Gcd(n % 10, gcd); if (gcd == 1) return 1; n /= 10; } return gcd; } static void SortArrayByGcd(int[] arr) { var list = arr.ToList(); list.Sort((o1, o2) => { var x = KeyFunc(o1) - KeyFunc(o2); if (x == 0) { if (o1 > o2) x = 1; else x = -1; } return x; }); Console.WriteLine(string.Join(" ", list)); } static void Main(string[] args) { int[] arr = { 555, 363, 488, 244 }; SortArrayByGcd(arr); }}// This code is contributed by aadityaburujwale. |
Javascript
<script>// JavaScript program for above approach// Function to calculate GCD of two integersfunction gcd(a, b) { // Base case if (b == 0) return a; // Recursively calculate GCD return gcd(b, a % b);}// Function to calculate GCD of// digits of array elementsfunction keyFunc(n) { let getGCD = String(n)[0] // Update the getGCD for (let i = 0; i < n; i++) getGCD = gcd(getGCD, i) // Return the resultant GCD return getGCD}// Function to sort an array in according// to GCD of digits of array elementsfunction sortArrayByGCD(arr) { // Sort the array arr.sort() // Sort the array according to gcd of // digits using comparator function arr = arr.sort(keyFunc) // Print the resultant array for (let i of arr) { document.write(i + " ") }}// Driver codelet arr = [555, 363, 488, 244];sortArrayByGCD(arr);</script> |
Output:
244 363 488 555
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
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!
