Given an array arr[] consisting of N integers, the task is to check if it is possible to divide the entire array into two arrays such that the sum of elements in new arrays is either both odd or both even. Also, each new array must have at least one element. If it is possible, print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {3, 1, 1, 1, 1, 1 }
Output: Yes
Explanation: The given array can be divided into two arrays as: {3, 1, 1, 1, 1} and {1}.Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: No
Explanation: No possible distribution exists such that both new arrays have either both odd or both even sum.
Approach: To solve the problem follow the below idea:
The idea is to observe the fact that if the count of odd numbers present in the given array is even, only then, the given array can be divided into two arrays having odd sum. If the count of odd numbers is odd, then one array will have odd number of odd elements & other will have even number of odd elements, and therefore answer will be “No”. Also, N should be greater than 1.
Follow the steps below to solve the problem:
- Check if N == 1, and print “No”.
- Find the total number of odd elements present in the given array and store it in a variable say, oddCnt.
- Check if oddcnt is even and N > 1, print “Yes”, else print “No”.
Below is the implementation of the above approach :
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;void canDivideArray(int arr[], int n){ // Create a variable to store // count of odd elements int oddCnt = 0; // Loop through all the array elements for (int i = 0; i < n; i++) { // If element is odd, then // increment the oddCnt if (arr[i] % 2 == 1) oddCnt++; } // If oddCnt is even and total number // of elements > 1, then print "Yes" if (oddCnt % 2 == 0 && n > 1) { cout << "Yes\n"; } // Otherwise print "No" else { cout << "NO\n"; }}// Driver code for the programint main(){ // Given array for example-1 int arr1[] = { 3, 1, 1, 1, 1, 1 }; int N1 = 6; canDivideArray(arr1, N1); // Given array for example-2 int arr2[] = { 1, 2, 3, 4, 5, 6 }; int N2 = 6; canDivideArray(arr2, N2); return 0;} |
Java
// Java code for the above approach:import java.io.*;class GFG { static void canDivideArray(int arr[], int n) { // Create a variable to store count of odd elements int oddCnt = 0; // Loop through all the array elements for (int i = 0; i < n; i++) { // If element is odd, then increment the oddCnt if (arr[i] % 2 == 1) oddCnt++; } // If oddCnt is even and total number of elements > // 1, then print "Yes" if (oddCnt % 2 == 0 && n > 1) { System.out.println("Yes"); } // Otherwise print "No" else { System.out.println("NO"); } } public static void main(String[] args) { // Given array for example-1 int[] arr1 = { 3, 1, 1, 1, 1, 1 }; int N1 = 6; canDivideArray(arr1, N1); // Given array for example-2 int[] arr2 = { 1, 2, 3, 4, 5, 6 }; int N2 = 6; canDivideArray(arr2, N2); }}// This code is contributed by sankar. |
Python3
def canDivideArray(arr, n): # Create a variable to store # count of odd elements oddCnt = 0 # Loop through all the array elements for i in range(n): # If element is odd, then # increment the oddCnt if arr[i] % 2 == 1: oddCnt += 1 # If oddCnt is even and total number # of elements > 1, then print "Yes" if oddCnt % 2 == 0 and n > 1: print("Yes") # Otherwise print "No" else: print("NO")# Given array for example-1arr1 = [3, 1, 1, 1, 1, 1]N1 = 6canDivideArray(arr1, N1)# Given array for example-2arr2 = [1, 2, 3, 4, 5, 6]N2 = 6canDivideArray(arr2, N2) |
C#
// C# code for the above approach:using System;public class GFG { static void canDivideArray(int[] arr, int n) { // Create a variable to store count of odd elements int oddCnt = 0; // Loop through all the array elements for (int i = 0; i < n; i++) { // If element is odd, then increment the oddCnt if (arr[i] % 2 == 1) oddCnt++; } // If oddCnt is even and total number of elements > // 1, then print "Yes" if (oddCnt % 2 == 0 && n > 1) { Console.WriteLine("Yes"); } // Otherwise print "No" else { Console.WriteLine("NO"); } } static public void Main() { // Code // Given array for example-1 int[] arr1 = { 3, 1, 1, 1, 1, 1 }; int N1 = 6; canDivideArray(arr1, N1); // Given array for example-2 int[] arr2 = { 1, 2, 3, 4, 5, 6 }; int N2 = 6; canDivideArray(arr2, N2); }}// This code is contributed by karthik. |
Javascript
function canDivideArray(arr, n) { // Create a variable to store count of odd elements let oddCnt = 0; // Loop through all the array elements for (let i = 0; i < n; i++) { // If element is odd, then increment the oddCnt if (arr[i] % 2 === 1) oddCnt++; } // If oddCnt is even and total number of elements > // 1, then print "Yes" if (oddCnt % 2 === 0 && n > 1) { console.log("Yes"); } // Otherwise print "No" else { console.log("NO"); }}// Given array for example-1const arr1 = [3, 1, 1, 1, 1, 1];const N1 = 6;canDivideArray(arr1, N1);// Given array for example-2const arr2 = [1, 2, 3, 4, 5, 6];const N2 = 6;canDivideArray(arr2, N2);// This Code is Contributed by Vikas Bishnoi |
Yes NO
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
