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 notbool 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 Codeint main(){ int arr[] = { 1, 1, 3 }; int N = sizeof(arr) / sizeof(arr[0]); check(arr, N); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Function to whether the array// can be made zero or notstatic 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 Codepublic 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 notdef 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 Codeif __name__ == '__main__': arr = [ 1, 1, 3]; N = len(arr); check(arr, N);# This code is contributed by 29AjayKumar |
C#
// C# implementation of the approachusing System;class GFG{ // Function to whether the array// can be made zero or notstatic 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 Codepublic 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 notfunction 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 Codelet 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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
