Maximice K que se puede reducir de Array para hacer que todos los elementos sean iguales

Dada una array arr[] de tamaño N , la tarea es hacer que todos los elementos sean iguales aplicando la operación dada a continuación cualquier número de veces (posiblemente cero) a cualquiera de los elementos de la array dada. 

• Seleccione un elemento en la array.
• Reducirlo por un entero positivo K .

Entre todos esos k positivos , imprima el máximo K.

Ejemplos :

Entrada : arr[] = {3, 7, 5, 3, 3, 7}
Salida : 2
Explicación : elija K = 2, disminuya ambos 7 dos veces y uno 5 una vez. para que todos los elementos sean iguales a 3 

Entrada : arr[] = {100, -2000, -2000, -2000}
Salida : 2100

Entrada: arr[] = {2, 2, 2}
Salida: -1
Explicación: Como todos los elementos ya son iguales, puede haber un número infinito de tales K posibles.

Enfoque : La tarea se puede resolver sobre la base de algunas observaciones. Todos los elementos de la array se pueden hacer iguales al elemento mínimo de la array. El K máximo se puede obtener encontrando el máximo común divisor de los elementos adyacentes en orden ordenado .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum value of K
int maxValue(int arr[], int N)
{
    // Sorting array of integers
    sort(arr, arr + N);
 
    // Initializing a variable
    int ans = 0;
 
    // Iterating using a for loop
    for (int i = 1; i < N; i++) {
 
        // Find the gcd of ans and
        // (arr[i] - arr[i - 1])
        ans = __gcd(ans, arr[i] - arr[i - 1]);
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
int main()
{
    // Initializing an array of integers
    int arr[] = { 3, 7, 5, 3, 3, 7 };
 
    // Number of elements in the array
    int N = sizeof(arr) / sizeof(int);
 
    int ans = maxValue(arr, N);
    if (ans > 0)
        cout << ans;
    else
        cout << "-1";
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
import java.math.BigInteger;
 
class GFG {
 
  //calculate gcd
  static int gcd(int a, int b)
  {
    return b == 0 ? a : gcd(b, a % b);  
  }
 
  // Function to find the maximum value of K
  static int maxValue(int arr[], int N)
  {
    // Sorting array of integers
    Arrays.sort(arr);
 
    // Initializing a variable
    int ans = 0;
 
    // Iterating using a for loop
    for (int i = 1; i < N; i++) {
 
      // Find the gcd of ans and
      // (arr[i] - arr[i - 1])
      ans = gcd(ans, arr[i] - arr[i - 1]);
    }
 
    // Return the answer
    return ans;
  }
 
  // Driver code
  public static void main (String[] args) {
    int arr[] = { 3, 7, 5, 3, 3, 7 };
 
    // Number of elements in the array
    int N = arr.length;
 
    int ans = maxValue(arr, N);
    if (ans > 0)
      System.out.println(ans);
    else
      System.out.println("-1");
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python program for the above approach
 
# calculate gcd
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b);
 
# Function to find the maximum value of K
def maxValue(arr, N):
    # Sorting array of integers
    arr.sort();
 
    # Initializing a variable
    ans = 0;
 
    # Iterating using a for loop
    for i in range(1,N):
       
        # Find the gcd of ans and
        # (arr[i] - arr[i - 1])
        ans = gcd(ans, arr[i] - arr[i - 1]);
 
    # Return the answer
    return ans;
 
# Driver code
if __name__ == '__main__':
    arr = [3, 7, 5, 3, 3, 7];
 
    # Number of elements in the array
    N = len(arr);
 
    ans = maxValue(arr, N);
    if (ans > 0):
        print(ans);
    else:
        print("-1");
 
# This code is contributed by shikhasingrajput

// C# program for the above approach
using System;
class GFG {
 
  // JavaScript code for the above approach
  static int __gcd(int a, int b)
  {
    // Everything divides 0
    if (a == 0)
      return b;
    if (b == 0)
      return a;
 
    // base case
    if (a == b)
      return a;
 
    // a is greater
    if (a > b)
      return __gcd(a - b, b);
    return __gcd(a, b - a);
  }
 
  // Function to find the maximum value of K
  static int maxValue(int[] arr, int N)
  {
 
    // Sorting array of integers
    Array.Sort(arr);
 
    // Initializing a variable
    int ans = 0;
 
    // Iterating using a for loop
    for (int i = 1; i < N; i++) {
 
      // Find the gcd of ans and
      // (arr[i] - arr[i - 1])
      ans = __gcd(ans, arr[i] - arr[i - 1]);
    }
 
    // Return the answer
    return ans;
  }
  public static void Main()
  {
    // Initializing an array of integers
    int[] arr = { 3, 7, 5, 3, 3, 7 };
 
    // Number of elements in the array
    int N = arr.Length;
 
    int ans = maxValue(arr, N);
    if (ans > 0)
      Console.Write(ans);
    else
      Console.Write(-1);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
       function __gcd(a, b) {
           // Everything divides 0
           if (a == 0)
               return b;
           if (b == 0)
               return a;
 
           // base case
           if (a == b)
               return a;
 
           // a is greater
           if (a > b)
               return __gcd(a - b, b);
           return __gcd(a, b - a);
       }
 
       // Function to find the maximum value of K
       function maxValue(arr, N)
       {
        
           // Sorting array of integers
           arr.sort(function (a, b) { return a - b })
 
           // Initializing a variable
           let ans = 0;
 
           // Iterating using a for loop
           for (let i = 1; i < N; i++) {
 
               // Find the gcd of ans and
               // (arr[i] - arr[i - 1])
               ans = __gcd(ans, arr[i] - arr[i - 1]);
           }
 
           // Return the answer
           return ans;
       }
 
       // Driver code
       // Initializing an array of integers
       let arr = [3, 7, 5, 3, 3, 7];
 
       // Number of elements in the array
       let N = arr.length;
 
       let ans = maxValue(arr, N);
       if (ans > 0)
           document.write(ans);
       else
           document.write(-1)
 
        // This code is contributed by Potta Lokesh
   </script>

2

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