两个二进制数组中的最小翻转，以便它们的XOR等于C ++中的另一个数组。
问题陈述
给定三个大小为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