Encuentre el número final obtenido después de realizar la operación dada

Dada una array de enteros positivos distintos arr[] , la tarea es encontrar el número final obtenido realizando la siguiente operación en los elementos de la array: 
Operación: Tomar dos números desiguales y reemplazar el número mayor con su diferencia hasta que todos los números se conviertan en igual.
Ejemplos: 
 

Entrada: arr[] = {5, 2, 3} 
Salida: 1 
5 – 3 = 2, arr[] = {2, 2, 3} 
3 – 2 = 1, arr[] = {2, 2, 1} 
2 – 1 = 1, arr[] = {2, 1, 1} 
2 – 1 = 1, arr[] = {1, 1, 1}
Entrada: arr[] = {3, 9, 6, 36} 
Salida : 3 
 

Enfoque ingenuo: dado que la respuesta final siempre será distinta, uno puede simplemente ordenar la array y reemplazar el término más grande con la diferencia de los dos elementos más grandes y repetir el proceso hasta que todos los números sean iguales.
Enfoque eficiente: A partir del algoritmo de Euclides , se sabe que mcd(a, b) = mcd(a – b, b) . Esto se puede extender a mcd(A ₁ , A ₂ , A ₃ , …, A _n ) = mcd(A ₁ – A ₂ , A ₂ , A ₃ , …, A _n ) . 
Además, digamos que después de aplicar la operación dada, el número final obtenido sea K. Por lo tanto, del algoritmo extendido, se puede decir que mcd(A ₁ , A ₂ , A ₃ , …, A _n ) = mcd(K , K, …, n veces) . Dado que mcd(K, K, …, n veces) = K , la solución del problema dado se puede encontrar 
encontrando el mcd de todos los elementos de la array.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the final number
// obtained after performing the
// given operation
int finalNum(int arr[], int n)
{
 
    // Find the gcd of the array elements
    int result = 0;
    for (int i = 0; i < n; i++) {
        result = __gcd(result, arr[i]);
    }
    return result;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 9, 6, 36 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << finalNum(arr, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the final number
// obtained after performing the
// given operation
static int finalNum(int arr[], int n)
{
 
    // Find the gcd of the array elements
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        result = __gcd(result, arr[i]);
    }
    return result;
}
 
static int __gcd(int a, int b)
{
    return b == 0? a:__gcd(b, a % b);    
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 9, 6, 36 };
    int n = arr.length;
 
    System.out.print(finalNum(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
from math import gcd as __gcd
 
# Function to return the final number
# obtained after performing the
# given operation
def finalNum(arr, n):
 
    # Find the gcd of the array elements
    result = arr[0]
    for i in arr:
        result = __gcd(result, i)
    return result
 
# Driver code
arr = [3, 9, 6, 36]
n = len(arr)
 
print(finalNum(arr, n))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the readonly number
// obtained after performing the
// given operation
static int finalNum(int []arr, int n)
{
 
    // Find the gcd of the array elements
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        result = __gcd(result, arr[i]);
    }
    return result;
}
 
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 3, 9, 6, 36 };
    int n = arr.Length;
 
    Console.Write(finalNum(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
// javascript implementation of the approach   
// Function to return the final number
    // obtained after performing the
    // given operation
    function finalNum(arr , n) {
 
        // Find the gcd of the array elements
        var result = 0;
        for (i = 0; i < n; i++) {
            result = __gcd(result, arr[i]);
        }
        return result;
    }
 
    function __gcd(a , b) {
        return b == 0 ? a : __gcd(b, a % b);
    }
 
    // Driver code
     
        var arr = [ 3, 9, 6, 36 ];
        var n = arr.length;
 
        document.write(finalNum(arr, n));
 
// This code contributed by aashish1995
</script>

3

Complejidad de tiempo: O (N * logN), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O (N) tiempo y la función _gcd tomará logN tiempo.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.