用 C++ 将数组总和变为偶数所需的最小移除数

问题表述

给定一个包含 N 个整数的数组 arr[]。我们需要编写一个程序来查找数组中需要移除的最小元素数，以便剩余元素的总和为偶数。

示例

如果输入数组为 {10, 20, 30, 5}，则我们需要移除一个元素，即 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

Narendra Kumar

更新日期： 2019-12-23

171 次浏览

开启你的 职业

通过完成课程获得认证

开始