সমস্যা বিবরণ
আকার n এর তিনটি অ্যারে দেওয়া আছে যেগুলো ০ এবং ১ দিয়ে গঠিত। কাজটি হল প্রথম এবং দ্বিতীয় অ্যারেতে ন্যূনতম বিট ফ্লিপ করাতে হবে যাতে প্রথম এবং দ্বিতীয় অ্যারেতে i-তম ইনডেক্স বিটর XOR তৃতীয় অ্যারেতে i-তম ইনডেক্স বিটর সমান হয়।
দয়া করে নোট করুন যে আমরা অ্যারে ১-এ সর্বোচ্চ p বিট এবং অ্যারে ২-এ সর্বোচ্চ 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) অথবা
ii. (arr1[i] == 1) এবং (arr2[i] == 1)
b. যদি arr3[i] == 1 তবে নিচের শর্তগুলো থেকে যেকোনো একটি সত্য:
i. (arr1[i] == 0) এবং (arr2[0] == 1) অথবা
ii. (arr1[i] == 1) এবং (arr2[i] == 0)
3. যদি ফ্লিপ প্রয়োজন হয় তবে আমরা arr1[i] বা arr2[i] যেকোনো একটি ফ্লিপ করতে পারি। অতএব আমরা নিষ্কর্ষ করতে পারি যে arr1 এবং arr2-এর XOR কে arr3-এর সমান করার জন্য প্রয়োজনীয় ফ্লিপ সংখ্যা p + q-এর চেয়ে কম বা সমান হতে হবে।
উদাহরণ (C++ কোড)
#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
