Check if X elements of an array can have an odd sum

Given an array of size N, find if we can choose any arbitrary X elements (X <= N) from this array that have an odd summation.

Examples :

Input : N = 5 X = 2 A = [1, 2, 3, 4, 5]
Output : Yes
Explanation :
We can choose 2 elements as {1, 2} which have an odd sum 3

Input : N = 3, X = 3, A = [11, 12, 13]
Output : No
Explanation :
No 3 elements have sum odd

Observations :

1. ODD/EVEN number of EVEN numbers have sum as EVEN.
2. ODD number of ODD numbers have sum as ODD.
3. EVEN number of ODD numbers have sum as EVEN.

Approach :

1. We iterate through the array and count the no of even numbers (say, xeven) and no of odd numbers (say, xodd)
2. Then we iterate from k = xodd to 0 backwards , taking into account only odd k
3. if we have k as odd, then we have (x – k) even numbers
4. if (x – k) is less than or equal to total number of even numbers ( xeven ), we have found the possibility “Yes”
5. if no such possibility after the loop ends, we print “No”

Implementation :

// C++ function to find if X elements from an array of size N have an Odd Sum
#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> &arr, int n, int x) {

  int xeven = 0, xodd = 0; // counter for even and odd
  for (auto x : arr)
    if (x & 1)
      xodd++;
    else
      xeven++;

  bool flag = false;// boolean flag to check if answer has been found

  for (int k = xodd; k >= 0; k--) {
    if ((k & 1) and (x - k) >= 0 and (x - k) <= xeven) {
      // if odd k adnd a valid (x - k)
      flag = true;
      break;
    }
  }

  cout << (flag ? "Yes" : "No") << endl;
}

// Driver code
int main() {

  int N = 5, X = 2;
  vector<int> arr = {1, 2, 3, 4, 5};
  solve(arr, N, X);

  return 0;
}

Yes

Time Complexity : O(N)