문제 설명
0과 1의 크기가 n인 세 개의 배열이 주어지면 첫 번째 및 두 번째 배열의 i번째 인덱스 비트의 XOR이 세 번째 배열입니다.
배열 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