Problem statement
ให้อาร์เรย์สามตัวที่ประกอบด้วย 0 และ 1 ขนาด n งานคือหาการพลิกบิตน้อยที่สุดในอาร์เรย์แรกและอาร์เรย์ที่สอง ทำให้ XOR ของบิตที่ index i ของอาร์เรย์แรกและสอง เท่ากับบิต index i ของอาร์เรย์ที่สาม
โปรดทราบว่าเราสามารถพลิกได้สูงสุด p บิตของอาร์เรย์ 1 และ q บิตของอาร์เรย์ 2 ไม่อนุญาตให้เรียงลำดับใหม่
สมมติ 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]) i.e (1 ^ 0) = 1 ซึ่งไม่เท่ากับ arr3[0] ต้องพลิก
- (arr1[1] ^ arr2[1]) i.e (0 ^ 1) = 1 เท่ากับ arr3[1] ไม่ต้องพลิก
- (arr1[2] ^ arr2[2]) i.e (1 ^ 0) = 1 เท่ากับ arr3[2] ไม่ต้องพลิก
- (arr1[3] ^ arr2[3]) i.e (1 ^ 1) = 0 เท่ากับ arr3[3] ไม่ต้องพลิก
- (arr1[4] ^ arr2[4]) i.e (0 ^ 0) = 0 เท่ากับ arr3[4] ไม่ต้องพลิก
- (arr1[5] ^ arr2[5]) i.e (1 ^ 0) = 1 ไม่เท่ากับ arr3[5] ต้องพลิก
- (arr1[6] ^ arr2[6]) i.e (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; }ผลลัพธ์
When you compile and execute the above program. It generates the following output −
Flips required: 3
