Số lần xóa tối thiểu để làm cho tổng mảng là số lẻ trong C ++

Tuyên bố vấn đề

Cho một mảng arr [] gồm N số nguyên. Chúng ta cần viết một chương trình để tìm số phần tử tối thiểu cần thiết để loại bỏ khỏi mảng, sao cho tổng các phần tử còn lại là số lẻ.

Ví dụ

Nếu mảng đầu vào là {10, 20, 30, 5, 7} thì chúng ta cần loại bỏ một phần tử tức là 5 hoặc 7 để tổng mảng là lẻ

Thuật toán

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

Ví dụ

#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;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Minimum required removals = 1