在 C++ 中移除数组元素使数组和为奇数所需的最小次数

问题陈述

给定一个整数数组 arr[] 和整数 N。我们需要编写一个程序，找到从数组中需要移除的元素的最小次数，以使剩余元素的总和为奇数。

示例

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

纳伦德拉·库马尔

更新时间：2019 年 12 月 23 日

185 次观看

开启 职业

通过完成课程获取认证

开始入门