Dada una array arr[] que consta de enteros positivos, la tarea es verificar si todos los elementos de la array dada se pueden convertir en 0 realizando la siguiente operación:
- Elija dos índices i y j tales que i != j y reste 1 tanto de arr[i] como de arr[j]
- La operación anterior se puede realizar cualquier número de veces
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: Sí
Explicación:
Primero, elija los valores 2 y 4 y realice la operación anterior 2 veces. Luego, la array se convierte en 1 0 3 2.
Ahora elija 1 y 3 y aplique la operación anterior una vez para obtener 0 0 2 2.
Ahora elija dos 2 y realice la operación anterior dos veces.
Finalmente, la array se convierte en 0 0 0 0.
Entrada: arr[] = {5, 5, 5, 5, 5}
Salida: No
Planteamiento: Al observar el problema detenidamente, se puede observar que si solo hay 1 elemento o la suma de todos los elementos es impar, entonces no es posible hacer que todos los elementos sean 0. Ya que en cada iteración, se resta 2 de la suma de todos los elementos, por lo tanto, la array puede convertirse en 0 solo si la suma de todos los elementos de la array es par. Y también, es posible hacer que la array sea 0 cuando el número más grande de la array es menor o igual que la suma de los elementos restantes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to make the array zero // by decrementing value in pairs #include <bits/stdc++.h> using namespace std; // Function to check if all the elements // can be made 0 in an array void canMake(int n, int ar[]) { // Variable to store // sum and maximum element // in an array int sum = 0, maxx = -1; // Loop to calculate the sum and max value // of the given array for (int i = 0; i < n; i++) { sum += ar[i]; maxx = max(maxx, ar[i]); } // If n is 1 or sum is odd or // sum - max element < max // then no solution if (n == 1 || sum % 2 == 1 || sum - maxx < maxx) { cout << "No\n"; } else { // For the remaining case, print Yes cout << "Yes\n"; } } // Driver code int main() { int n = 6; int arr[] = { 1, 1, 2, 3, 6, 11 }; canMake(n, arr); return 0; }
Java
// Java program to make the array zero // by decrementing value in pairs class GFG { // Function to check if all the elements // can be made 0 in an array static void canMake(int n, int ar[]) { // Variable to store // sum and maximum element // in an array int sum = 0, maxx = -1; // Loop to calculate the sum and max value // of the given array for (int i = 0; i < n; i++) { sum += ar[i]; maxx = Math.max(maxx, ar[i]); } // If n is 1 or sum is odd or // sum - max element < max // then no solution if (n == 1 || sum % 2 == 1 || sum - maxx < maxx) { System.out.print("No\n"); } else { // For the remaining case, print Yes System.out.print("Yes\n"); } } // Driver code public static void main(String[] args) { int n = 6; int arr[] = { 1, 1, 2, 3, 6, 11 }; canMake(n, arr); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to make the array zero # by decrementing value in pairs # Function to check if all the elements # can be made 0 in an array def canMake(n, ar) : # Variable to store # sum and maximum element # in an array sum = 0; maxx = -1; # Loop to calculate the sum and max value # of the given array for i in range(n) : sum += ar[i]; maxx = max(maxx, ar[i]); # If n is 1 or sum is odd or # sum - max element < max # then no solution if (n == 1 or sum % 2 == 1 or sum - maxx < maxx) : print("No"); else : # For the remaining case, print Yes print("Yes"); # Driver code if __name__ == "__main__" : n = 6; arr = [ 1, 1, 2, 3, 6, 11 ]; canMake(n, arr); # This code is contributed by AnkitRai01
C#
// C# program to make the array zero // by decrementing value in pairs using System; class GFG { // Function to check if all the elements // can be made 0 in an array static void canMake(int n, int []ar) { // Variable to store // sum and maximum element // in an array int sum = 0, maxx = -1; // Loop to calculate the sum and max value // of the given array for (int i = 0; i < n; i++) { sum += ar[i]; maxx = Math.Max(maxx, ar[i]); } // If n is 1 or sum is odd or // sum - max element < max // then no solution if (n == 1 || sum % 2 == 1 || sum - maxx < maxx) { Console.Write("No\n"); } else { // For the remaining case, print Yes Console.Write("Yes\n"); } } // Driver code public static void Main(String[] args) { int n = 6; int []arr = { 1, 1, 2, 3, 6, 11 }; canMake(n, arr); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript program to make the array zero // by decrementing value in pairs // Function to check if all the elements // can be made 0 in an array function canMake(n, ar) { // Variable to store // sum and maximum element // in an array var sum = 0, maxx = -1; // Loop to calculate the sum and max value // of the given array for (var i = 0; i < n; i++) { sum += ar[i]; maxx = Math.max(maxx, ar[i]); } // If n is 1 or sum is odd or // sum - max element < max // then no solution if (n == 1 || sum % 2 == 1 || sum - maxx < maxx) { document.write( "No"); } else { // For the remaining case, print Yes document.write( "Yes"); } } // Driver code var n = 6; var arr = [1, 1, 2, 3, 6, 11]; canMake(n, arr); </script>
Yes
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA