Số lần xóa tối thiểu để tổng mảng thành số chẵn trong C++

Đề bài

Cho mảng arr[] gồm N số nguyên. Cần viết chương trình tìm số lượng phần tử tối thiểu cần xóa khỏi mảng để tổng các phần tử còn lại là số chẵn.

Ví dụ

Nếu mảng đầu vào là {10, 20, 30, 5} thì cần xóa một phần tử là 5 để tổng mảng thành số chẵn.

Thuật toán

1. Tổng bất kỳ số lượng số chẵn nào luôn là số chẵn.
2. Tổng số lẻ các số lẻ luôn là số lẻ.
3. Tổng số chẵn các số lẻ luôn là số chẵn.
4. Đếm số phần tử lẻ trong mảng. Nếu số lượng phần tử lẻ là chẵn, không cần xóa phần tử nào; nếu là lẻ thì xóa 1 phần tử lẻ bất kỳ.

Ví dụ mã C++

#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) ? 0 : 1;
}

int main() {
    int arr[] = {10, 20, 30, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Số lần xóa tối thiểu = " << getMinRemovals(arr, n) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số lần xóa tối thiểu = 1