Número máximo que puede dividir todos los elementos de la array después de un reemplazo

Dada una array arr , reemplace cualquier elemento de la array con cualquier otro entero. La tarea es devolver el número máximo que divide completamente todos los elementos de esta array.

Ejemplos:

Entrada: arr = [15, 9, 3]
Salida:  3
Explicación: Aquí reemplaza 15 con 3 para que el arreglo se convierta en arr = [3, 9, 3] y ahora todos los elementos en el arreglo son divisibles por 3, entonces 3 es nuestra respuesta

Entrada: arr = [16, 5, 10, 25]
Salida:  5

Enfoque: Para resolver el problema anterior:

• Iterar la array sobre el entero i de cero a menos que su longitud
• Cada vez, elimine el i-ésimo elemento de la array y encuentre el máximo común divisor y almacene en la variable el mcd
• Actualice maxGcd si el gcd actual es mayor que maxGcd
   

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

// C++ Implementation for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return gcd of two numbers
int gcdOfTwoNos(int num1, int num2)
{
 
    // If one of numbers is 0
    // then gcd is other number
    if (num1 == 0)
        return num2;
    if (num2 == 0)
        return num1;
 
    // If both are equal
    // then that value is gcd
    if (num1 == num2)
        return num1;
 
    // One is greater
    if (num1 > num2)
        return gcdOfTwoNos(num1 - num2, num2);
    return gcdOfTwoNos(num1, num2 - num1);
}
 
// Function to return minimum sum
int Min_sum(int arr[], int N)
{
    // Initialize min_sum with large value
    int min_sum = 1000000, maxGcd = 1;
    for (int i = 0; i < N; i++) {
 
        // Initialize variable gcd
        int gcd;
        if (i == 0)
            gcd = arr[1];
        else {
            gcd = arr[i - 1];
        }
        for (int j = 0; j < N; j++) {
            if (j != i)
                gcd = gcdOfTwoNos(gcd, arr[j]);
        }
 
        // Storing value of arr[i] in c
        int c = arr[i];
 
        // Update maxGcd if gcd is greater
        // than maxGcd
        if (gcd > maxGcd)
            maxGcd = gcd;
    }
 
    // returning the maximum divisor
    // of all elements
    return maxGcd;
}
// Driver code
int main()
{
    int arr[] = { 16, 5, 10, 25 };
    int N = sizeof(arr) / sizeof(int);
    cout << Min_sum(arr, N);
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG
{
   
  // Function to return gcd of two numbers
static int gcdOfTwoNos(int num1, int num2)
{
 
    // If one of numbers is 0
    // then gcd is other number
    if (num1 == 0)
        return num2;
    if (num2 == 0)
        return num1;
 
    // If both are equal
    // then that value is gcd
    if (num1 == num2)
        return num1;
 
    // One is greater
    if (num1 > num2)
        return gcdOfTwoNos(num1 - num2, num2);
    return gcdOfTwoNos(num1, num2 - num1);
}
 
// Function to return minimum sum
static int Min_sum(int arr[], int N)
{
    // Initialize min_sum with large value
    int min_sum = 1000000, maxGcd = 1;
    for (int i = 0; i < N; i++) {
 
        // Initialize variable gcd
        int gcd;
        if (i == 0)
            gcd = arr[1];
        else {
            gcd = arr[i - 1];
        }
        for (int j = 0; j < N; j++) {
            if (j != i)
                gcd = gcdOfTwoNos(gcd, arr[j]);
        }
 
        // Storing value of arr[i] in c
        int c = arr[i];
 
        // Update maxGcd if gcd is greater
        // than maxGcd
        if (gcd > maxGcd)
            maxGcd = gcd;
    }
 
    // returning the maximum divisor
    // of all elements
    return maxGcd;
}
   
// Driver code
    public static void main (String[] args) {
      int arr[] = { 16, 5, 10, 25 };
      int N = arr.length;
   
        System.out.println( Min_sum(arr, N));
    }
}
 
// This code is contributed by Potta Lokesh

# Python 3 Implementation for the above approach
 
# Function to return gcd1 of two numbers
def gcd1OfTwoNos(num1, num2):
    # If one of numbers is 0
    # then gcd1 is other number
    if (num1 == 0):
        return num2
    if (num2 == 0):
        return num1
 
    # If both are equal
    # then that value is gcd1
    if (num1 == num2):
        return num1
 
    # One is greater
    if (num1 > num2):
        return gcd1OfTwoNos(num1 - num2, num2)
    return gcd1OfTwoNos(num1, num2 - num1)
 
# Function to return minimum sum
def Min_sum(arr, N):
    # Initialize min_sum with large value
    min_sum = 1000000
    maxgcd1 = 1
    for i in range(N):
        # Initialize variable gcd1
        gcd1 = 1
        if (i == 0):
            gcd1 = arr[1]
        else:
            gcd1 = arr[i - 1]
        for j in range(N):
            if (j != i):
                gcd1 = gcd1OfTwoNos(gcd1, arr[j])
 
        # Storing value of arr[i] in c
        c = arr[i]
 
        # Update maxgcd1 if gcd1 is greater
        # than maxgcd1
        if (gcd1 > maxgcd1):
            maxgcd1 = gcd1
 
    # returning the maximum divisor
    # of all elements
    return maxgcd1
 
# Driver code
if __name__ == '__main__':
    arr = [16, 5, 10, 25]
    N = len(arr)
    print(Min_sum(arr, N))
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for the above approach
 
using System;
 
public class GFG
{
   
  // Function to return gcd of two numbers
static int gcdOfTwoNos(int num1, int num2)
{
 
    // If one of numbers is 0
    // then gcd is other number
    if (num1 == 0)
        return num2;
    if (num2 == 0)
        return num1;
 
    // If both are equal
    // then that value is gcd
    if (num1 == num2)
        return num1;
 
    // One is greater
    if (num1 > num2)
        return gcdOfTwoNos(num1 - num2, num2);
    return gcdOfTwoNos(num1, num2 - num1);
}
 
// Function to return minimum sum
static int Min_sum(int []arr, int N)
{
    // Initialize min_sum with large value
    int min_sum = 1000000, maxGcd = 1;
    for (int i = 0; i < N; i++) {
 
        // Initialize variable gcd
        int gcd;
        if (i == 0)
            gcd = arr[1];
        else {
            gcd = arr[i - 1];
        }
        for (int j = 0; j < N; j++) {
            if (j != i)
                gcd = gcdOfTwoNos(gcd, arr[j]);
        }
 
 
        // Update maxGcd if gcd is greater
        // than maxGcd
        if (gcd > maxGcd)
            maxGcd = gcd;
    }
 
    // returning the maximum divisor
    // of all elements
    return maxGcd;
}
   
// Driver code
    public static void Main (string[] args) {
      int []arr = { 16, 5, 10, 25 };
      int N = arr.Length;
   
        Console.WriteLine(Min_sum(arr, N));
    }
}
 
// This code is contributed by AnkThon

  <script>
        // JavaScript Program to implement
        // the above approach
 
  // Function to return gcd of two numbers
function gcdOfTwoNos(num1, num2)
{
 
    // If one of numbers is 0
    // then gcd is other number
    if (num1 == 0)
        return num2;
    if (num2 == 0)
        return num1;
 
    // If both are equal
    // then that value is gcd
    if (num1 == num2)
        return num1;
 
    // One is greater
    if (num1 > num2)
        return gcdOfTwoNos(num1 - num2, num2);
    return gcdOfTwoNos(num1, num2 - num1);
}
 
// Function to return minimum sum
function Min_sum(arr, N)
{
    // Initialize min_sum with large value
    let min_sum = 1000000, maxGcd = 1;
    for (let i = 0; i < N; i++) {
 
        // Initialize variable gcd
        let gcd;
        if (i == 0)
            gcd = arr[1];
        else {
            gcd = arr[i - 1];
        }
        for (let j = 0; j < N; j++) {
            if (j != i)
                gcd = gcdOfTwoNos(gcd, arr[j]);
        }
 
        // Storing value of arr[i] in c
        let c = arr[i];
 
        // Update maxGcd if gcd is greater
        // than maxGcd
        if (gcd > maxGcd)
            maxGcd = gcd;
    }
 
    // returning the maximum divisor
    // of all elements
    return maxGcd;
}
         
 // Driver Code
         
      let arr = [ 16, 5, 10, 25 ];
      let N = arr.length;
   
      document.write( Min_sum(arr, N));
 
// This code is contributed by sanjoy_62.
    </script>

5

Complejidad de tiempo: O ((N ^ 2) * Log (M)), donde M es el valor mínimo en la array
Espacio auxiliar: O (1)