Check if all elements of the given array can be made 0 by decrementing value in pairs
Given an array arr[] consisting of positive integers, the task is to check if all elements of the given array can be made 0 by performing the following operation:
- Choose two indices i and j such that i != j and subtract 1 from both arr[i] and arr[j]
- The above operation can be performed any number of times
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: Yes
Explanation:
First, choose values 2 and 4 and perform the above operation 2 times. Then the array becomes 1 0 3 2.
Now choose 1 and 3 and apply above operation once to get 0 0 2 2.
Now pick two 2s and perform the above operation twice.
Finally array becomes 0 0 0 0.
Input: arr[] = {5, 5, 5, 5, 5}
Output: No
Approach: On observing the problem carefully, it can be observed that if there is only 1 element or the sum of all the elements is odd, then it is not possible to make all elements 0. Since at every iteration, 2 is being subtracted from the sum of all elements, therefore, the array can become 0 only if the sum of all elements of the array is even. And also, it is possible to make the array 0 when the largest number in the array is less than or equal to the sum of remaining elements.
Below is the implementation of the above approach:
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
Time Complexity: O(N)
Auxiliary Space: O(1)