Số lần lật bit tối thiểu trong hai mảng nhị phân để XOR bằng mảng thứ ba trong C++

Đề bài

Cho ba mảng 0/1 cùng kích thước n. Tìm số lần lật bit tối thiểu ở mảng 1 và 2 sao cho XOR của hai mảng bằng mảng 3. Giới hạn: tối đa p lần lật mảng 1, q lần lật mảng 2. Không được sắp xếp lại.

Ví dụ p=2, q=5:

arr1 = {1,0,1,1,0,1,0}
arr2 = {0,1,0,1,0,0,1}
arr3 = {0,1,1,0,0,0,0}

So sánh từng vị trí: (arr1[i] ^ arr2[i]) == arr3[i] thì không cần lật, ngược lại cần lật.

Thuật toán

1. Nếu (arr1[i] ^ arr2[i]) == arr3[i] thì bỏ qua.
2. Nếu khác thì cần lật:
   a. Nếu arr3[i] == 0: (arr1[i]==0 và arr2[i]==0) HOẶC (arr1[i]==1 và arr2[i]==1)
   b. Nếu arr3[i] == 1: (arr1[i]==0 và arr2[i]==1) HOẶC (arr1[i]==1 và arr2[i]==0)
3. Số lần lật cần thiết ≤ p + q.

Ví dụ mã C++

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int laySoLacCanThiet(int *arr1, int *arr2, int *arr3, int n, int p, int q){
    int flips = 0;
    for (int i = 0; i < n; ++i) {
        if ((arr1[i] ^ arr2[i]) != arr3[i]) {
            ++flips;
        }
    }
    return flips <= (p + q) ? flips : -1;
}

int main(){
    int arr1[] = {1, 0, 1, 1, 0, 1, 0};
    int arr2[] = {0, 1, 0, 1, 0, 0, 1};
    int arr3[] = {0, 1, 1, 0, 0, 0, 0};
    int size = SIZE(arr1);
    cout << "Số lần lật cần: " << laySoLacCanThiet(arr1, arr2, arr3, size, 2, 5) << "\n";
    return 0;
}

Kết quả đầu ra

Số lần lật cần: 3