给定三个大小为n的0和1的数组，任务是在第一和第二数组中找到最小的位翻转，以使第一和第二数组的第i个索引位的XOR等于第一个数组的第i个索引位第三数组。
请注意，我们最多只能翻转数组1的最多p位和数组2的最多q位。而且，不允许重新排列数组元素。
让我们假设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}（arr1 [0] ^ arr2 [0]）即（1 ^ 0）= 1，不等于arr3 [0]。因此，需要翻转。
（arr1 [1] ^ arr2 [1]），即（0 ^ 1）= 1，等于arr3 [1]。因此，不需要翻转。
（arr1 [2] ^ arr2 [2]），即（1 ^ 0）= 1，等于arr3 [2]。因此，不需要翻转。
（arr1 [3] ^ arr2 [3]），即（1 ^ 1）= 0，等于arr3 [3]。因此，不需要翻转。
（arr1 [4] ^ arr2 [4]），即（0 ^ 0）= 0，等于arr3 [4]。因此，不需要翻转。
（arr1 [5] ^ arr2 [5]），即（1 ^ 0）= 1，不等于arr3 [5]。因此，需要翻转。
（arr1 [6] ^ arr2 [6]）即（0 ^ 1）= 1，不等于arr3 [6]。因此，需要翻转。
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.
#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;
}输出结果
当您编译并执行上述程序时。它生成以下输出-
Flips required: 3