C++で配列の合計を奇数にするための最小限の削除

問題の説明

N個の整数の配列arr[]が与えられます。残りの要素の合計が奇数になるように、配列から削除する必要のある要素の最小数を見つけるプログラムを作成する必要があります。

例

入力配列が{10、20、30、5、7}の場合、配列の合計を奇数にするために1つの要素、つまり5または7を削除する必要があります

アルゴリズム

1. Sum of any number of even numbers is always even
2. Sum of odd numbers of odd numbers is always odd
3. Sum of odd numbers of even times is always even
4. Count the number of odd elements in the array. If the count of odd elements in the array is even, then we need to remove single element from the array but if the count of odd elements in the array is odd then there is no need to remove any element

例

#include <bits/stdc++.h>
using namespace std;
int getMinRemovals(int *arr, int n) {
   int cnt = 0;
   for (int i = 0; i < n; ++i) {
      if (arr[i] % 2 == 1) {
         ++cnt;
      }
   }
   return (cnt % 2 == 0) ? 1 : 0;
}
int main() {
   int arr[] = {10, 20, 30, 5, 7};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Minimum required removals = " <<
   getMinRemovals(arr, n) << endl;
   return 0;
}

上記のプログラムをコンパイルして実行する場合。次の出力を生成します

出力

Minimum required removals = 1