在 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 次觀看

開啟 職業

透過完成課程獲取認證

開始入門