# Check if it is possible to split given Array into K odd-sum subsets

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:YesExplanation:

[1], [3, 4, 7, 5], [3] and [1] are the possible subsets.Input:K = 3, arr[] = {2, 3, 4, 7, 2}Output:NoExplanation:

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` `// subsets` `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)` ` ` `cnt += 1;` ` ` `}` ` ` `// Check if split is possible` ` ` `if` `(cnt >= k && cnt % 2 == k % 2)` ` ` `return` `true` `;` ` ` `else` ` ` `return` `false` `;` `}` `// Driver Program` `int` `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 sum` `class` `GFG{` ` ` `// Function to check if array` `// can be split in required K` `// subsets` `static` `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 code` `public` `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` `# subsets` `def` `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 Code` `if` `__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 sum` `using` `System;` `class` `GFG{` `// Function to check if array` `// can be split in required K` `// subsets` `static` `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 code` `public` `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)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.