Compruebe si al menos la mitad de la array se puede reducir a cero realizando algunas operaciones

Dada una array de elementos n-positivos. En cada operación, puede seleccionar algunos elementos y disminuirlos en 1 y aumentar los elementos restantes en m. La tarea es determinar si después de algunas iteraciones es posible tener al menos la mitad de los elementos de la array dada igual a cero o no.
Ejemplos : 
 

Input : arr[] = {3, 5, 6, 8}, m = 2 
Output : Yes

Input : arr[] = {4, 7, 12, 13, 34},  m = 7
Output : No

Si tratamos de analizar el enunciado del problema, encontraremos que en cualquier paso estás disminuyendo un elemento en 1 o aumentándolo en m. Eso significa que en cada paso realizado, hay un total de tres posibilidades si comparamos dos elementos.
Sean a1 y a2 dos elementos entonces: 
 

1. Ambos elementos se redujeron en 1 y, por lo tanto, no hubo cambios en su diferencia real.
2. Ambos elementos aumentaron en m y, por lo tanto, no hubo cambios en su diferencia real nuevamente.
3. Un elemento disminuyó en 1 y otro aumentó en m y, por lo tanto, resultó un cambio de (m + 1) en su diferencia real.

Significa que en cada paso mantendrá la diferencia entre dos elementos iguales o la aumentará en (m+1).
Entonces, si toma el módulo de todos los elementos por (m+1) y mantiene su frecuencia, podemos verificar cuántos elementos se pueden hacer iguales a cero en cualquier momento.
Algoritmo:
 

• Crear una tabla hash de tamaño m+1
• Capture la frecuencia de los elementos como (arr[i] % (m+1)) y almacénela en una tabla hash.
• Averigüe la frecuencia máxima y si es mayor o igual a n/2, entonces la respuesta es SÍ, de lo contrario, NO.

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

// C++ program to find whether half-array
// reducible to 0
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the desired
// result after computation
void isHalfReducible(int arr[], int n, int m)
{
    int frequencyHash[m + 1];
    int i;
 
    memset(frequencyHash, 0, sizeof(frequencyHash));
    for (i = 0; i < n; i++) {
        frequencyHash[arr[i] % (m + 1)]++;
    }
 
    for (i = 0; i <= m; i++) {
        if (frequencyHash[i] >= n / 2)
            break;
    }
 
    if (i <= m)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 8, 16, 32, 3, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int m = 7;
 
    isHalfReducible(arr, n, m);
 
    return 0;
}

// Java Program to find whether half-array
// reducible to 0
 
public class GFG {
 
    // Function to print the desired
    // result after computation
    static void isHalfReducible(int arr[], int n, int m)
    {
        int frequencyHash[] = new int[m + 1];
        int i;
 
        for(i = 0 ; i < frequencyHash.length ; i++)
            frequencyHash[i] = 0 ;
        
        for (i = 0; i < n; i++) {
            frequencyHash[arr[i] % (m + 1)]++;
        }
 
        for (i = 0; i <= m; i++) {
            if (frequencyHash[i] >= n / 2)
                break;
        }
 
        if (i <= m)
            System.out.println("Yes") ;
        else
            System.out.println("No") ;
    }
 
// Driver code
    public static void main(String args[])
    {
            int arr[] = { 8, 16, 32, 3, 12 };
            int n = arr.length ;
 
            int m = 7;
 
            isHalfReducible(arr, n, m);
 
    }
    // This code is contributed by ANKITRAI1
}

# Python3 program to find whether
# half-array reducible to 0
 
# Function to print the desired
# result after computation
def isHalfReducible(arr, n, m):
     
    frequencyHash =[0]*(m + 1);
    i = 0;
    while(i < n):
        frequencyHash[(arr[i] % (m + 1))] += 1;
        i += 1;
 
    i = 0;
    while(i <= m):
        if(frequencyHash[i] >= (n / 2)):
            break;
        i += 1;
 
    if (i <= m):
        print("Yes");
    else:
        print("No");
 
# Driver Code
arr = [ 8, 16, 32, 3, 12 ];
n = len(arr);
 
m = 7;
isHalfReducible(arr, n, m);
     
# This code is contributed by mits

// C# Program to find whether half-array
// reducible to 0
 
using System;
 
  
public class GFG {
  
    // Function to print the desired
    // result after computation
    static void isHalfReducible(int[] arr, int n, int m)
    {
        int[] frequencyHash = new int[m + 1];
        int i;
  
        for(i = 0 ; i < frequencyHash.Length ; i++)
            frequencyHash[i] = 0 ;
         
        for (i = 0; i < n; i++) {
            frequencyHash[arr[i] % (m + 1)]++;
        }
  
        for (i = 0; i <= m; i++) {
            if (frequencyHash[i] >= n / 2)
                break;
        }
  
        if (i <= m)
            Console.WriteLine("Yes") ;
        else
            Console.WriteLine("No") ;
    }
  
// Driver code
    public static void Main()
    {
            int[] arr = { 8, 16, 32, 3, 12 };
            int n = arr.Length ;
  
            int m = 7;
  
            isHalfReducible(arr, n, m);
  
    }
    // This code is contributed by Subhadeep
}

<?php
// PHP program to find whether 
// half-array reducible to 0
 
// Function to print the desired
// result after computation
function isHalfReducible($arr, $n, $m)
{
    $frequencyHash = array_fill(0, $m + 1, 0);
    $i = 0;
    for (;$i < $n; $i++)
    {
        $frequencyHash[($arr[$i] % ($m + 1))]++;
    }
 
    for ($i = 0; $i <= $m; $i++)
    {
        if ($frequencyHash[$i] >= ($n / 2))
            break;
    }
 
    if ($i <= $m)
        echo "Yes\n";
    else
        echo "No\n";
}
 
// Driver Code
$arr = array( 8, 16, 32, 3, 12 );
$n = sizeof($arr);
 
$m = 7;
isHalfReducible($arr, $n, $m);
     
// This code is contributed by mits
?>

<script>
 
// javascript program to find whether half-array
// reducible to 0
 
// Function to print the desired
// result after computation
function isHalfReducible(arr, n, m)
{
    var frequencyHash = Array(m+1).fill(0);
    var i;
 
    for (i = 0; i < n; i++) {
        frequencyHash[arr[i] % (m + 1)]++;
    }
 
    for (i = 0; i <= m; i++) {
        if (frequencyHash[i] >= n / 2)
            break;
    }
 
    if (i <= m)
        document.write( "Yes" );
    else
        document.write( "No" );
}
 
// Driver Code
var arr = [ 8, 16, 32, 3, 12 ];
var n = arr.length;
var m = 7;
isHalfReducible(arr, n, m);
 
</script>

Yes

Tiempo Complejidad : O(n+m)
Espacio Auxiliar : O(m)