Số lần xóa tối thiểu để tổng mảng thành số lẻ 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ố lẻ.

Ví dụ

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

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, cần xóa 1 phần tử; nếu là lẻ thì không cần xóa phần tử nào.

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

int main() {
    int arr[] = {10, 20, 30, 5, 7};
    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