সমস্যা বিবৃতি
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. যদি (arr1[i] ^ arr2[i]) ==arr3[i] তাহলে ফ্লিপের প্রয়োজন নেই বলে চালিয়ে যান।2। যদি (arr1[i] ^ arr2[i]) !=arr3[i] তাহলে ফ্লিপ করতে হবে। ক arr3[i] ==0 হলে নিচের শর্তগুলির মধ্যে একটি সত্য:i. (arr1[i] ==0) এবং (arr2[i] ==0) বা ii. (arr1[i] ==1) এবং (arr2[i] ==1) খ. arr3[i] ==1 হলে নিচের শর্তগুলির মধ্যে একটি সত্য:i. (arr1[i] ==0) এবং (arr2[0] ==1) বা ii. (arr1[i] ==1) এবং (arr2[i] ==0)3. যদি ফ্লিপের প্রয়োজন হয় তবে আমরা হয় arr1[i] বা arr2[i] ফ্লিপ করতে পারি। তাই আমরা এই উপসংহারে পৌঁছাতে পারি যে arr1 এর XOR এবং arr2 এর সমান arr3 তৈরি করতে প্রয়োজনীয় ফ্লিপের সংখ্যা p + q এর থেকে কম বা সমান হওয়া উচিত।উদাহরণ
#include#fine SIZE(arr) (sizeof(arr) / sizeof(arr[0]))Namespace ব্যবহার করে std;int getRequiredFlips(int *arr1, int *arr2, int *arr3, int n, int p, int q){ int flips =0; জন্য (int i =0; i আউটপুট
আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেউল্টানো প্রয়োজন:3