समस्या कथन
0 और 1 के आकार n के साथ तीन सरणियों को देखते हुए, कार्य पहले और दूसरे सरणी में बिट्स के न्यूनतम फ्लिप को खोजने के लिए है जैसे कि पहले और दूसरे सरणी के i'th इंडेक्स बिट का XOR i'th इंडेक्स बिट के बराबर है तीसरी सरणी।
कृपया ध्यान दें कि हम केवल सरणी 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