C++에서 배열 합을 홀수로 만들기 위한 최소 제거

문제 설명

N 정수의 배열 arr[]이 주어집니다. 배열에서 제거해야 하는 최소 요소 수를 찾는 프로그램을 작성해야 나머지 요소의 합이 홀수가 됩니다.

예

입력 배열이 {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