C++ 中如何用最少的移除次数使数组和为奇数
c++server side programmingprogramming
问题描述
给定一个包含 N 个整数的数组 arr[]。我们需要编写一个程序，找出需要从数组中移除的最少元素个数，使得剩余元素的和为奇数。
示例
如果输入数组为 {10, 20, 30, 5, 7}，则需要移除一个元素，即 5 或 7，以使数组和为奇数
算法
1. 任意数量的偶数之和始终为偶数 2. 奇数个奇数之和始终为奇数 3. 偶数个奇数之和始终为偶数 4. 计算数组中奇数元素的数量。如果数组中奇数元素的数量是偶数，那么我们需要从数组中删除单个元素，但如果数组中奇数元素的数量是奇数，则无需删除任何元素
示例
#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
