XORがC++の別の配列と等しくなるように、2つのバイナリ配列の最小フリップ。

問題の説明

サイズnの0と1の3つの配列が与えられた場合、タスクは、1番目と2番目の配列のi番目のインデックスビットのXORがi番目のインデックスビットと等しくなるように、1番目と2番目の配列のビットの最小フリップを見つけることです。 3番目の配列。

反転できるのは、配列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