Given an array arr[] of length N, the task is to check if it is possible to split the given array into K non-empty and non-intersecting subsets such that the sum of elements of each subset is odd.
Examples:
Input: K = 4, arr[] = {1, 3, 4, 7, 5, 3, 1}
Output: Yes
Explanation:
[1], [3, 4, 7, 5], [3] and [1] are the possible subsets.
Input: K = 3, arr[] = {2, 3, 4, 7, 2}
Output: No
Explanation:
Given array cannot be split into 3 subset with odd sum.
Approach:
To solve the problem mentioned above we need to observe the following points:
- Even numbers don’t change the parity of the sum of subsets, so we can ignore them.
- If number of odd integers in the array is less than K, then we cannot split it into K subsets with odd sums since there are not enough odd integers.
- Let number of odd integers be cnt. Then, the answer will always be possible only if cnt % 2 = K % 2. This is because we will distribute one odd number in the first K-1 subsets and cnt – K – 1 odd numbers in the last subset. Now since cnt and K have the same parity so cnt – K – 1 will be odd and the sum is also odd.
Hence, to solve the problem, count the number of odd integers present in the array. Let this be cnt. The answer will be ‘Yes’ if cnt is greater than K and cnt % 2 = K % 2. Otherwise, an answer is not possible and we print ‘No’.
Below is the implementation of the above approach:
C++
// C++ implementation to check if it is// possible to split array into K// subsets with odd sum#include <bits/stdc++.h>using namespace std;// Function to check if array// can be split in required K// subsetsbool checkArray(int n, int k, int arr[]){ // Store count of // odd numbers int cnt = 0; for (int i = 0; i < n; i++) { // Check if element // is odd if (arr[i] & 1) cnt += 1; } // Check if split is possible if (cnt >= k && cnt % 2 == k % 2) return true; else return false;}// Driver Programint main(){ int arr[] = { 1, 3, 4, 7, 5, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 4; if (checkArray(n, k, arr)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation to check if it // is possible to split array into K// subsets with odd sumclass GFG{ // Function to check if array// can be split in required K// subsetsstatic boolean checkArray(int n, int k, int arr[]){ // Store count of odd numbers int cnt = 0; for(int i = 0; i < n; i++) { // Check if element is odd if ((arr[i] & 1) != 0) cnt += 1; } // Check if split is possible if (cnt >= k && cnt % 2 == k % 2) return true; else return false;}// Driver codepublic static void main (String []args){ int arr[] = { 1, 3, 4, 7, 5, 3, 1 }; int n = arr.length; int k = 4; if (checkArray(n, k, arr)) System.out.print("Yes"); else System.out.print("No");}}// This code is contributed by chitranayal |
Python3
# Python3 implementation to check if # it is possible to split array into # K subsets with odd sum# Function to check if array# can be split in required K# subsetsdef checkArray(n, k, arr): # Store count of # odd numbers cnt = 0 for i in range(n): # Check if element # is odd if (arr[i] & 1): cnt += 1 # Check if split is possible if (cnt >= k and cnt % 2 == k % 2): return True else: return False# Driver Codeif __name__ == '__main__': arr = [ 1, 3, 4, 7, 5, 3, 1 ] n = len(arr) k = 4 if (checkArray(n, k, arr)): print("Yes") else: print("No")# This code is contributed by mohit kumar 29 |
C#
// C# implementation to check if it // is possible to split array into K// subsets with odd sumusing System;class GFG{// Function to check if array// can be split in required K// subsetsstatic bool checkArray(int n, int k, int []arr){ // Store count of odd numbers int cnt = 0; for(int i = 0; i < n; i++) { // Check if element is odd if ((arr[i] & 1) != 0) cnt += 1; } // Check if split is possible if (cnt >= k && cnt % 2 == k % 2) return true; else return false;}// Driver codepublic static void Main (string []args){ int []arr = { 1, 3, 4, 7, 5, 3, 1 }; int n = arr.Length; int k = 4; if (checkArray(n, k, arr)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed by AnkitRai01 |
Javascript
<script>// javascript implementation to check if it // is possible to split array into K// subsets with odd sum // Function to check if array // can be split in required K // subsets function checkArray(n , k , arr) { // Store count of odd numbers var cnt = 0; for (i = 0; i < n; i++) { // Check if element is odd if ((arr[i] & 1) != 0) cnt += 1; } // Check if split is possible if (cnt >= k && cnt % 2 == k % 2) return true; else return false; } // Driver code var arr = [ 1, 3, 4, 7, 5, 3, 1 ]; var n = arr.length; var k = 4; if (checkArray(n, k, arr)) document.write("Yes"); else document.write("No");// This code contributed by gauravrajput1</script> |
Output:
Yes
Time Complexity: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
