C++でも配列の合計を作成するための最小限の削除

問題の説明

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

例

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

アルゴリズム

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 do not need to remove any element from the array but if the count of odd elements in the array is odd then by removing any one of the odd elements from the array

例

#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) ? 0 : 1;
}
int main() {
   int arr[] = {10, 20, 30, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Minimum required removals = " << getMinRemovals(arr, n) << endl;
   return 0;
}

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

出力

Minimum required removals = 1