Haga que todos los elementos de la array sean iguales mediante la resta repetida de la diferencia absoluta de pares de su máximo

Dada una array arr[] que consta de N enteros, la tarea es igualar todos los elementos de la array seleccionando cualquier par de enteros de la array y reemplazando el entero más grande del par con su diferencia absoluta cualquier cantidad de veces. Imprime el valor final de todos los elementos de la array.

Ejemplos:

Entrada: arr[] ={2, 3, 4}
Salida: 1
Explicación: 
Paso 1: Realizar en el par (2, 3) modifica arr[] = {2, 1, 4}
Paso 2: Realizar en el par ( 2, 4) modifica arr[] = {2, 1, 2}
Paso 3: Actuar en el par (2, 1) modifica {1, 1, 2}
Paso 4: Actuar en el par (1, 2) modifica arr [] = {1, 1, 1}

Entrada: arr[] = {24, 60}
Salida: 12

Enfoque: A partir del enunciado del problema anterior, se puede observar que para cualquier par (a, b) , la diferencia absoluta se resta del elemento máximo. Entonces esta operación es similar a encontrar el MCD del par . Por lo tanto, a partir de esta observación, está claro que todos los elementos del arreglo deben reducirse al GCD del arreglo. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable gcd como 1 .
• Recorra la array dada y, mientras recorre, actualice gcd como:

 mcd = mcd(arr[i], mcd) , donde 0 ≤ i < N

• Después del paso anterior, el valor de gcd es el elemento de array requerido después de aplicar la operación dada a cada par distinto de elementos.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return
// gcd of a and b
int gcd(int a, int b)
{
  // Base Case
  if (a == 0)
    return b;
 
  // Recursive Call
  return gcd(b % a, a);
}
 
// Function to find gcd of array
int findGCD(int arr[], int N)
{
  // Initialise the result
  int result = 0;
 
  // Traverse the array arr[]
  for (int i = 0; i < N; i++)
  {
    // Update result as gcd of
    // the result and arr[i]
    result = gcd(result, arr[i]);
 
    if (result == 1)
    {
      return 1;
    }
  }
 
  // Return the resultant GCD
    return result;
}
 
// Driver Code
int main()
{
  // Given array arr[]
  int arr[] = {2, 3, 4};
 
  int N = sizeof(arr) /
          sizeof(arr[0]);
 
  // Function Call
  cout << findGCD(arr, N);
  return 0;
}
 
// This code is contributed by 29AjayKumar

// Java program for the above approach
 
public class GCD {
 
    // Function to return gcd of a and b
    static int gcd(int a, int b)
    {
        // Base Case
        if (a == 0)
            return b;
 
        // Recursive Call
        return gcd(b % a, a);
    }
 
    // Function to find gcd of array
    static int findGCD(int arr[], int N)
    {
        // Initialise the result
        int result = 0;
 
        // Traverse the array arr[]
        for (int element : arr) {
 
            // Update result as gcd of
            // the result and arr[i]
            result = gcd(result, element);
 
            if (result == 1) {
                return 1;
            }
        }
 
        // Return the resultant GCD
        return result;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array arr[]
        int arr[] = { 2, 3, 4 };
 
        int N = arr.length;
 
        // Function Call
        System.out.println(findGCD(arr, N));
    }
}

# Python3 program for the above approach
 
# Function to return gcd of a and b
def gcd(a, b):
     
    # Base Case
    if (a == 0):
        return b
 
    # Recursive call
    return gcd(b % a, a)
 
# Function to find gcd of array
def findGCD(arr, N):
     
    # Initialise the result
    result = 0
 
    # Traverse the array arr[]
    for element in arr:
 
        # Update result as gcd of
        # the result and arr[i]
        result = gcd(result, element)
 
        if (result == 1):
            return 1
 
    # Return the resultant GCD
    return result
 
# Driver Code
 
# Given array arr[]
arr = [ 2, 3, 4 ]
 
N = len(arr)
 
# Function call
print(findGCD(arr, N))
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
 
class GFG{
 
// Function to return gcd of a and b
static int gcd(int a, int b)
{
     
    // Base Case
    if (a == 0)
        return b;
 
    // Recursive call
    return gcd(b % a, a);
}
 
// Function to find gcd of array
static int findGCD(int[] arr, int N)
{
     
    // Initialise the result
    int result = 0;
 
    // Traverse the array arr[]
    foreach(int element in arr)
    {
 
        // Update result as gcd of
        // the result and arr[i]
        result = gcd(result, element);
 
        if (result == 1)
        {
            return 1;
        }
    }
 
    // Return the resultant GCD
    return result;
}
 
// Driver Code
public static void Main()
{
     
    // Given array arr[]
    int[] arr = { 2, 3, 4 };
 
    int N = arr.Length;
 
    // Function call
    Console.WriteLine(findGCD(arr, N));
}
}
 
// This code is contributed by sanjoy_62

<script>
 
// JavaScript program for
// the above approach
 
    // Function to return gcd of a and b
    function gcd(a, b)
    {
        // Base Case
        if (a == 0)
            return b;
  
        // Recursive Call
        return gcd(b % a, a);
    }
  
    // Function to find gcd of array
    function findGCD(arr, N)
    {
        // Initialise the result
        let result = 0;
  
        // Traverse the array arr[]
        for (let element in arr) {
  
            // Update result as gcd of
            // the result and arr[i]
            result = gcd(result, element);
  
            if (result == 1) {
                return 1;
            }
        }
  
        // Return the resultant GCD
        return result;
    }
 
// Driver code
 
          // Given array arr[]
        let arr = [ 2, 3, 4 ];
  
        let N = arr.length;
  
        // Function Call
        document.write(findGCD(arr, N));
                             
</script>

1

Complejidad de tiempo: O(N*logN), donde N es el tamaño de la array dada.
Espacio Auxiliar: O(N)