C++ এ k সেট বিট সহ একটি সংখ্যাকে সর্বাধিক করার জন্য ন্যূনতম ফ্লিপস প্রয়োজন।

সমস্যা বিবৃতি

দুটি সংখ্যা n এবং k দেওয়া হলে, প্রদত্ত সংখ্যাটিকে সর্বাধিক করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ফ্লিপগুলি খুঁজে বের করতে হবে এর বিটগুলিকে ফ্লিপ করে যাতে ফলাফলপ্রাপ্ত সংখ্যাটির ঠিক k সেট বিট থাকে। অনুগ্রহ করে মনে রাখবেন ইনপুট অবশ্যই শর্ত পূরণ করবে যে k

উদাহরণ

ধরা যাক n =9 এবং k =2
9-এর বাইনারি উপস্থাপনা হল −1001৷ এতে 4 বিট রয়েছে৷
2 সেট বিট সহ বৃহত্তম 4 সংখ্যার বাইনারি সংখ্যা হল − 1100 অর্থাৎ 12
1001 থেকে 1100 রূপান্তর করতে আমাদের হাইলাইট করা 2 বিট ফ্লিপ করতে হবে

অ্যালগরিদম

<পূর্ব>1. n এ বিটের সংখ্যা গণনা করুন। আসুন আমরা এই ভেরিয়েবলটিকে bitCount হিসাবে কল করি। আমরা গণিত লাইব্রেরি থেকে log2(n) ফাংশনটি ফ্লো হিসাবে ব্যবহার করতে পারি:bitCount =log2(n) + 1;2। নিচের মত k সেট বিট সহ বৃহত্তম সংখ্যা খুঁজুন:maxNum =pow(2, k) - 1;3। k সেট বিটগুলির সাথে সম্ভাব্য বৃহত্তম সংখ্যাটি সন্ধান করুন এবং নীচের মতো n এর মতো ঠিক একই সংখ্যক বিট রয়েছে:maxNum =maxNum <<(bitCount - k);4। গণনা করুন (n^ maxNum) এবং সেট বিটের সংখ্যা গণনা করুন।

উদাহরণ

#include #include নেমস্পেস ব্যবহার করে std;int getSetBits(int n){ int cnt =0; যখন (n) { ++cnt; n =n &(n - 1); } রিটার্ন cnt;}int minFlipsRequired(int n, int k){int bitCount, maxNum, flipCount; bitCount =log2(n) + 1; maxNum =pow(2, k)- 1; maxNum =maxNum <<(bitCount - k); flipCount =n ^ maxNum; ফেরত getSetBits(flipCount);}int main(){ cout <<"ন্যূনতম প্রয়োজনীয় ফ্লিপস:" < আউটপুট
 
 আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
 তৈরি করে সর্বনিম্ন প্রয়োজনীয় ফ্লিপ:2