Check if given array can be made 0 with given operations performed any number of times
Given an array arr[] containing N integers, the task is to find whether all the elements of the given array can be made 0 by following operations:
- Increment any element by 2.
- Subtract the minimum element of the array from all elements in the array.
- The above operations can be performed any number times.
If all the elements of the given array can become zero then print Yes else print No.
Examples:
Input: arr[] = {1, 1, 3}
Output: Yes
Explanation:
1st round: Choose the first element in the array and increase it by 2 i.e arr[] = {3, 1, 3}.
Then decrease all the elements by 1(which is minimum in the current array) i.e arr[] = {2, 0, 2}.
2nd round: Choose the second element in the array and increase it by 2 i.e arr[] = {2, 2, 2}.
Then decrease all the elements by 2(which is minimum in the current array) i.e arr[] = {0, 0, 0}.
Therefore, with the given operations performing on the elements of the array, all the elements of the given array can be reduced to 0.
Input: arr[] = {2, 1, 4, 2}
Output: No
Explanation:
We cannot make all the element of the array 0 by performing the given operations.
Approach: The problem can be solved with the help of Parity.
- Since, by incrementing the element of the array by 2 in each operation, the parity of the element is not changed i.e., odd remains odd or even remains even.
- And after subtracting each element of the array with the minimum element in the array, the parity of even integers becomes odd and the parity of odd integers becomes even.
- Therefore to make all the elements of the array 0, the parity of all the elements must be same otherwise we can’t make all the elements of the array 0 by the given operations.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to whether the array // can be made zero or not bool check( int arr[], int N) { // Count for even elements int even = 0; // Count for odd elements int odd = 0; // Traverse the array to // count the even and odd for ( int i = 0; i < N; i++) { // If arr[i] is odd if (arr[i] & 1) { odd++; } // If arr[i] is even else { even++; } } // Check if count of even // is zero or count of odd // is zero if (even == N || odd == N) cout << "Yes" ; else cout << "No" ; } // Driver's Code int main() { int arr[] = { 1, 1, 3 }; int N = sizeof (arr) / sizeof (arr[0]); check(arr, N); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG{ // Function to whether the array // can be made zero or not static void check( int arr[], int N) { // Count for even elements int even = 0 ; // Count for odd elements int odd = 0 ; // Traverse the array to // count the even and odd for ( int i = 0 ; i < N; i++) { // If arr[i] is odd if (arr[i] % 2 == 1 ) { odd++; } // If arr[i] is even else { even++; } } // Check if count of even // is zero or count of odd // is zero if (even == N || odd == N) System.out.print( "Yes" ); else System.out.print( "No" ); } // Driver's Code public static void main(String[] args) { int arr[] = { 1 , 1 , 3 }; int N = arr.length; check(arr, N); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function to whether the array # can be made zero or not def check(arr, N): # Count for even elements even = 0 ; # Count for odd elements odd = 0 ; # Traverse the array to # count the even and odd for i in range (N): # If arr[i] is odd if (arr[i] % 2 = = 1 ): odd + = 1 ; # If arr[i] is even else : even + = 1 ; # Check if count of even # is zero or count of odd # is zero if (even = = N or odd = = N): print ( "Yes" ); else : print ( "No" ); # Driver's Code if __name__ = = '__main__' : arr = [ 1 , 1 , 3 ]; N = len (arr); check(arr, N); # This code is contributed by 29AjayKumar |
C#
// C# implementation of the approach using System; class GFG{ // Function to whether the array // can be made zero or not static void check( int []arr, int N) { // Count for even elements int even = 0; // Count for odd elements int odd = 0; // Traverse the array to // count the even and odd for ( int i = 0; i < N; i++) { // If arr[i] is odd if (arr[i] % 2 == 1) { odd++; } // If arr[i] is even else { even++; } } // Check if count of even // is zero or count of odd // is zero if (even == N || odd == N) Console.Write( "Yes" ); else Console.Write( "No" ); } // Driver's Code public static void Main(String[] args) { int []arr = { 1, 1, 3 }; int N = arr.Length; check(arr, N); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // Function to whether the array // can be made zero or not function check(arr, N) { // Count for even elements let even = 0; // Count for odd elements let odd = 0; // Traverse the array to // count the even and odd for (let i = 0; i < N; i++) { // If arr[i] is odd if (arr[i] & 1) { odd++; } // If arr[i] is even else { even++; } } // Check if count of even // is zero or count of odd // is zero if (even == N || odd == N) document.write( "Yes" ); else document.write( "No" ); } // Driver's Code let arr = [ 1, 1, 3 ]; let N = arr.length; check(arr, N); // This code is contributed by gfgking </script> |
Yes
Time Complexity: O(N), where N is the length of the given array.
Auxiliary Space: O(1)
Contact Us