Ordenar una array en orden creciente de GCD de sus dígitos

Dada una array arr[] que consta de N enteros positivos, la tarea es ordenar la array arr[] de acuerdo con el orden creciente de GCD de los dígitos de cada elemento . Si el GCD de dos o más elementos es el mismo, ordene según sus valores.

Ejemplos:

Entrada: arr[] = {555, 363, 488, 244}
Salida: 244 363 488 555
Explicación:
Siguiendo el MCD de los dígitos de cada número:

1. 555: MCD(5, 5, 5) = 5.
2. 363: MCD(3, 6, 3) = 3.
3. 488: MCD(4, 8, 8) = 4.
4. 244: MCD(2, 4, 4) = 2.

Después de ordenar según los criterios dados, el orden de los elementos es {244, 363, 488, 555}.

Entrada: arr[] = {555, 363, 488, 244, 444, 5}
Salida: 244 363 444 488 5 555

Enfoque: El problema dado se puede resolver usando la función de comparación con la función sort() . La función de comparación se define como:

• Toma dos argumentos a la vez y devuelve verdadero si el GCD del primer argumento es menor que el segundo argumento.
• Si el valor de GCD es el mismo, devuelve verdadero si el primer argumento es menor que el segundo argumento. De lo contrario, devuelve falso .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to calculate GCD of two integers
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 elements
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;
}
 
// 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 elements
void 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 code
int main()
{
    vector<int>arr = { 555, 363, 488, 244 };;
    sortArrayByGCD(arr);
}
 
// This code is contributed by nirajgusain5

// Java program for the above approach
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
class GFG{
     
// Function to calculate GCD of two integers
static 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 elements
static 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 elements
public 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 code
public static void main(String[] args)
{
    int arr[] = { 555, 363, 488, 244 };
    sortArrayByGCD(arr);
}
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to calculate
# GCD of two integers
def 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 elements
def 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 elements
def 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 array
arr = [555, 363, 488, 244]
sortArrayByGCD(arr)

<script>
 
// JavaScript program for above approach
 
// Function to calculate GCD of two integers
function 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 elements
function 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 elements
function 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 code
let arr = [555, 363, 488, 244];
sortArrayByGCD(arr);
 
</script>

244 363 488 555

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)