Incrementos mínimos para hacer que todos los elementos de la array sean iguales con la suma igual a la array dada después de exactamente una eliminación

Dada una array arr[] de tamaño N y un número entero K , la tarea es verificar si todos los elementos de la array pueden igualarse eliminando un elemento de la array e incrementando el valor de todos los demás elementos de la array de manera que la suma total de los elementos de la array sigue siendo el mismo. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba “NO” .

Ejemplos:

Entrada: arr[] = { 2, 2, 2, 3 } 
Salida : SÍ 
Explicación: 
Eliminar arr[2] (indexación basada en 0) de la array e incrementar todos los demás elementos en 1 modifica arr[] a { 3, 3 , 3 } 
Dado que todos los elementos del arreglo son iguales. Por lo tanto, la salida requerida es «SÍ».

Entrada: arr[] = { 0, 3, 0 }, K = 3 
Salida: : NO 
Eliminar arr[1] (indexación basada en 0) de la array e incrementar el valor arr[0] en 1 y arr[2] by 2 modifica arr[] a { 1, 2 } 
Dado que todos los elementos de la array no son iguales. Por lo tanto, la salida requerida es «NO».

Enfoque: El problema se puede resolver usando la técnica Greedy . La idea es eliminar el elemento de array más grande e incrementar el valor de otros elementos de modo que la suma total permanezca igual. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos secMax , para almacenar el segundo elemento más grande de la array .
• Inicialice una variable, digamos totalSum , para almacenar la suma de los elementos de la array .
• Recorra la array y calcule la suma de los elementos de la array y encuentre el segundo elemento de array más grande.
• Si totalSum < (N – 1) * secMax o totalSum % (N – 1) != 0 , entonces imprima “NO” .
• De lo contrario, escriba “SI” .

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 check if an array of
// equal elements with sum equal to
// the given array can be obtained or not
bool CheckAllarrayEqual(int arr[], int N)
{
    // Base case
    if (N == 1) {
        return true;
    }
 
    // Stores sum of
    // array elements
    int totalSum = arr[0];
 
    // Stores second largest
    // array element
    int secMax = INT_MIN;
 
    // Stores the largest
    // array element
    int Max = arr[0];
 
    // Traverse the array
    for (int i = 1; i < N; i++) {
 
        if (arr[i] >= Max) {
 
            // Update secMax
            secMax = Max;
 
            // Update Max
            Max = arr[i];
        }
        else if (arr[i] > secMax) {
 
            // Update secMax
            secMax = arr[i];
        }
 
        // Update totalSum
        totalSum += arr[i];
    }
 
    // If totalSum is less than
    // secMax * (N - 1))
    if ((secMax * (N - 1)) > totalSum) {
 
        return false;
    }
 
    // If totalSum is not
    // divisible by (N - 1)
    if (totalSum % (N - 1)) {
 
        return false;
    }
 
    return true;
}
 
// Driver Code
int main()
{
    int arr[] = { 6, 2, 2, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    if (CheckAllarrayEqual(arr, N)) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
}

// Java program to implement
// the above approach
import java.util.*;
    
class GFG{
 
// Function to check if an array of
// equal elements with sum equal to
// the given array can be obtained or not
static boolean CheckAllarrayEqual(int[] arr,
                                  int N)
{
     
    // Base case
    if (N == 1)
    {
        return true;
    }
   
    // Stores sum of
    // array elements
    int totalSum = arr[0];
   
    // Stores second largest
    // array element
    int secMax = Integer.MIN_VALUE;
   
    // Stores the largest
    // array element
    int Max = arr[0];
   
    // Traverse the array
    for(int i = 1; i < N; i++)
    {
        if (arr[i] >= Max)
        {
             
            // Update secMax
            secMax = Max;
             
            // Update Max
            Max = arr[i];
        }
        else if (arr[i] > secMax)
        {
             
            // Update secMax
            secMax = arr[i];
        }
         
        // Update totalSum
        totalSum += arr[i];
    }
   
    // If totalSum is less than
    // secMax * (N - 1))
    if ((secMax * (N - 1)) > totalSum)
    {
        return false;
    }
   
    // If totalSum is not
    // divisible by (N - 1)
    if (totalSum % (N - 1) != 0)
    {
        return false;
    }
   
    return true;
}
    
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 6, 2, 2, 2 };
    int N = arr.length;
   
    if (CheckAllarrayEqual(arr, N))
    {
        System.out.print("YES");
    }
    else
    {
        System.out.print("NO");
    }
}
}
 
// This code is contributed by susmitakundugoaldanga

# Python3 program to implement
# the above approach
 
# Function to check if an array of
# equal elements with sum equal to
# the given array can be obtained or not
def CheckAllarrayEqual(arr, N):
     
    # Base case
    if (N == 1):
        return True
 
    # Stores sum of
    # array elements
    totalSum = arr[0]
 
    # Stores second largest
    # array element
    secMax = -10**19
 
    # Stores the largest
    # array element
    Max = arr[0]
 
    # Traverse the array
    for i in range(1,N):
 
        if (arr[i] >= Max):
 
            # Update secMax
            secMax = Max
 
            # Update Max
            Max = arr[i]
        elif (arr[i] > secMax):
 
            # Update secMax
            secMax = arr[i]
 
        # Update totalSum
        totalSum += arr[i]
 
    # If totalSum is less than
    # secMax * (N - 1))
    if ((secMax * (N - 1)) > totalSum):
 
        return False
 
    # If totalSum is not
    # divisible by (N - 1)
    if (totalSum % (N - 1)):
        return False
    return True
 
# Driver Code
if __name__ == '__main__':
    arr=[6, 2, 2, 2]
    N = len(arr)
 
    if (CheckAllarrayEqual(arr, N)):
        print("YES")
    else:
        print("NO")
 
        # This code is contributed by mohit kumar 29

// C# program to implement
// the above approach 
using System;
class GFG
{
  
// Function to check if an array of
// equal elements with sum equal to
// the given array can be obtained or not
static bool CheckAllarrayEqual(int[] arr, int N)
{
    // Base case
    if (N == 1) {
        return true;
    }
  
    // Stores sum of
    // array elements
    int totalSum = arr[0];
  
    // Stores second largest
    // array element
    int secMax = Int32.MinValue;
  
    // Stores the largest
    // array element
    int Max = arr[0];
  
    // Traverse the array
    for (int i = 1; i < N; i++) {
  
        if (arr[i] >= Max) {
  
            // Update secMax
            secMax = Max;
  
            // Update Max
            Max = arr[i];
        }
        else if (arr[i] > secMax) {
  
            // Update secMax
            secMax = arr[i];
        }
  
        // Update totalSum
        totalSum += arr[i];
    }
  
    // If totalSum is less than
    // secMax * (N - 1))
    if ((secMax * (N - 1)) > totalSum) {
  
        return false;
    }
  
    // If totalSum is not
    // divisible by (N - 1)
    if (totalSum % (N - 1) != 0) {
  
        return false;
    }
  
    return true;
}
  
// Driver Code
public static void Main()
{
    int[] arr = { 6, 2, 2, 2 };
    int N = arr.Length;
  
    if (CheckAllarrayEqual(arr, N)) {
        Console.Write("YES");
    }
    else {
        Console.Write("NO");
    }
}
}
 
// This code is contributed by sanjoy_62

<script>
 
// JavaScript program to implement
// the above approach
 
 
// Function to check if an array of
// equal elements with sum equal to
// the given array can be obtained or not
function CheckAllarrayEqual(arr,N)
{
     
    // Base case
    if (N == 1)
    {
        return true;
    }
 
    // Stores sum of
    // array elements
    let totalSum = arr[0];
 
    // Stores second largest
    // array element
    let secMax = Number.MIN_VALUE;
 
    // Stores the largest
    // array element
    let Max = arr[0];
 
    // Traverse the array
    for(let i = 1; i < N; i++)
    {
        if (arr[i] >= Max)
        {
             
            // Update secMax
            secMax = Max;
             
            // Update Max
            Max = arr[i];
        }
        else if (arr[i] > secMax)
        {
             
            // Update secMax
            secMax = arr[i];
        }
         
        // Update totalSum
        totalSum += arr[i];
    }
 
    // If totalSum is less than
    // secMax * (N - 1))
    if ((secMax * (N - 1)) > totalSum)
    {
        return false;
    }
 
    // If totalSum is not
    // divisible by (N - 1)
    if (totalSum % (N - 1) != 0)
    {
        return false;
    }
 
    return true;
}
     
// Driver Code
 
    let arr = [ 6, 2, 2, 2 ];
    let N = arr.length;
 
    if (CheckAllarrayEqual(arr, N))
    {
        document.write("YES");
    }
    else
    {
        document.write("NO");
    }
 
 
// This code is contributed by sravan kumar Gottumukkala
 
</script>

YES

Complejidad temporal: O(N)  
Espacio auxiliar: O(1)