Tuyên bố vấn đề
Cho ba mảng với số 0 và 1 có kích thước n, nhiệm vụ là tìm số lần lật nhỏ nhất của các bit trong mảng thứ nhất và thứ hai sao cho XOR của bit chỉ số thứ i của mảng thứ nhất và thứ hai bằng với bit chỉ số thứ i của mảng thứ ba.
Xin lưu ý rằng chúng ta chỉ có thể lật nhiều nhất p bit của mảng 1 và nhiều nhất q bit của mảng 2. Ngoài ra, việc sắp xếp lại các phần tử của mảng cũng không được phép.
Giả sử p =2 và 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} - (arr1 [0] ^ arr2 [0]) tức là (1 ^ 0) =1 không bằng arr3 [0]. Do đó, cần phải lật.
-
(arr1 [1] ^ arr2 [1]) tức là (0 ^ 1) =1 bằng arr3 [1]. Do đó, không cần lật.
-
(arr1 [2] ^ arr2 [2]) tức là (1 ^ 0) =1 bằng arr3 [2]. Do đó, không cần lật.
-
(arr1 [3] ^ arr2 [3]) tức là (1 ^ 1) =0 bằng arr3 [3]. Do đó, không cần lật.
-
(arr1 [4] ^ arr2 [4]) tức là (0 ^ 0) =0 bằng arr3 [4]. Do đó, không cần lật.
-
(arr1 [5] ^ arr2 [5]) tức là (1 ^ 0) =1 không bằng arr3 [5]. Do đó, cần phải lật.
-
(arr1 [6] ^ arr2 [6]) tức là (0 ^ 1) =1 không bằng arr3 [6]. Do đó, cần phải lật.
Thuật toán
1. If (arr1[i] ^ arr2[i]) == arr3[i] then continue as flip is not required. 2. If (arr1[i] ^ arr2[i]) != arr3[i] then flip is required. a. If arr3[i] == 0 then one of the following condition is true: i. (arr1[i] == 0) and (arr2[i] == 0) OR ii. (arr1[i] == 1) and (arr2[i] == 1) b. If arr3[i] == 1 then one of the following condition is true: i. (arr1[i] == 0) and (arr2[0] == 1) OR ii. (arr1[i] == 1) and (arr2[i] == 0) 3. If flip is required then we can either flip arr1[i] or arr2[i]. Hence we can conclude that number of flips required to make XOR of arr1 and arr2 equal to arr3 should be less than or equal to p + q.
Ví dụ
#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getRequiredFlips(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 << "Flips required: " << getRequiredFlips(arr1, arr2, arr3, size, 2, 5) << "\n";
return 0;
} Đầu ra
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 -
Flips required: 3