समस्या कथन
आकार 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. यदि (arr1[i] ^ arr2[i]) == arr3[i] तो जारी रखें क्योंकि फ्लिप आवश्यक नहीं है। 2. यदि (arr1[i] ^ arr2[i]) != arr3[i] तो फ्लिप आवश्यक है। a. यदि arr3[i] == 0 तो निम्नलिखित में से एक कंडीशन सत्य है: i. (arr1[i] == 0) और (arr2[i] == 0) OR ii. (arr1[i] == 1) और (arr2[i] == 1) b. यदि arr3[i] == 1 तो निम्नलिखित में से एक कंडीशन सत्य है: i. (arr1[i] == 0) और (arr2[0] == 1) OR ii. (arr1[i] == 1) और (arr2[i] == 0) 3. यदि फ्लिप आवश्यक है तो हम या तो arr1[i] या arr2[i] फ्लिप कर सकते हैं। इसलिए हम निष्कर्ष निकाल सकते हैं कि arr1 और arr2 के XOR को arr3 के बराबर बनाने के लिए आवश्यक फ्लिप्स की संख्या 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
