Số bước tối thiểu làm tất cả phần tử mảng chia hết cho 4 trong C++

Đề bài

Cho mảng kích thước n, nhiệm vụ là tìm số bước tối thiểu cần thiết để làm cho tất cả các phần tử của mảng chia hết cho 4. Một bước được định nghĩa là loại bỏ bất kỳ hai phần tử nào từ mảng và thêm tổng của hai phần tử này vào mảng.

Ví dụ

Nếu mảng đầu vào là {1, 2, 0, 2, 4, 3} thì cần 3 phép toán –

1 + 3 = 4
2 + 2 = 4
0 + 4 = 4

Thuật toán

1. Tổng tất cả phần tử mảng phải chia hết cho 4. Nếu không, bài toán không thể.
2. Khởi tạo mảng modulus kích thước 4 với giá trị 0.
3. Khởi tạo bộ đếm = 0. Theo dõi số bước đã thực hiện.
4. Duyệt mảng đầu vào và lấy modulus 4 của mỗi phần tử.
5. Tăng giá trị modulus[mod] trong mảng modulus lên 1.
6. modulus[0] là số phần tử đã chia hết cho 4. Không cần ghép cặp.
7. modulus[1] và modulus[3] có thể kết hợp để được số chia hết cho 4. Tăng count lên min của cả hai.
8. Mỗi 2 phần tử modulus[2] có thể kết hợp để được phần tử chia hết cho 4.
9. Với các phần tử còn lại, tăng modulus[2] thêm một nửa modulus[1] và modulus[3].
10. Tăng count thêm một nửa modulus[2]. Lấy nửa vì mỗi 2 phần tử gộp thành 1.
11. Giá trị cuối cùng của count là số bước cần để chuyển tất cả phần tử mảng chia hết cho 4.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

int getMinRequiredSteps(int arr[], int n) {
    int count = 0;
    int modulus[4] = {0};
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int mod = arr[i] % 4;
        sum += mod;
        modulus[mod]++;
    }
    if (sum % 4 != 0) {
        return -1;
    } else {
        if (modulus[1] > modulus[3]) {
            count += modulus[3];
        } else {
            count += modulus[1];
        }
        modulus[1] -= count;
        modulus[3] -= count;
        modulus[2] += modulus[1] / 2;
        modulus[2] += modulus[3] / 2;
        count += modulus[1] / 2;
        count += modulus[3] / 2;
        count += modulus[2] / 2;
        return count;
    }
}

int main() {
    int arr[] = {1, 2, 0, 2, 4, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Số bước tối thiểu cần = " << getMinRequiredSteps(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ố bước tối thiểu cần = 2