সমস্যা বিবরণ
দুটি সংখ্যা n এবং k দেওয়া আছে। আমাদের ন্যূনতম কতগুলো বিট ফ্লিপ করলে দিয়ে गये নম্বরটি k সেট বিটস সহ সর্বোচ্চ হয়ে যাবে তা বের করতে হবে। দয়া করে নোট করুন ইনপুট অবশ্যই শর্ত পূরণ করতে হবে যে k < n-এ বিট সংখ্যা।
উদাহরণ
- মনে করুন n = 9 এবং k = 2
- 9-এর বাইনারি রিপ্রেজেন্টেশন - 1001। এতে ৪টি বিট আছে।
- ২ সেট বিটস সহ সর্বোচ্চ ৪ ডিজিট বাইনারি নম্বর - 1100 অর্থাৎ ১২
- 1001 কে 1100 এ কনভার্ট করতে হাইলাইট করা ২টি বিট ফ্লিপ করতে হবে
অ্যালগরিদম
1. n-এ বিট সংখ্যা কাউন্ট করো। এটাকে bitCount ভেরিয়েবল বলব। আমরা math লাইব্রেরি থেকে log2(n) ফাংশন ব্যবহার করতে পারি:
bitCount = log2(n) + 1;
2. k সেট বিটস সহ সর্বোচ্চ নম্বর বের করো:
maxNum = pow(2, k) - 1;
3. n-এর সমান বিট সংখ্যা সহ k সেট বিটস যুক্ত সর্বোচ্চ সম্ভাব্য নম্বর বের করো:
maxNum = maxNum << (bitCount - k);
4. (n ^ maxNum) ক্যালকুলেট করো এবং সেট বিটস কাউন্ট করো।
উদাহরণ (C++ কোড)
#include <iostream>
#include <cmath>
using namespace std;
int getSetBits(int n) {
int cnt = 0;
while (n) {
++cnt;
n = n & (n - 1);
}
return 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;
return getSetBits(flipCount);
}
int main() {
cout << "Minimum required flips: " << minFlipsRequired(9, 2) << "\n";
return 0;
}
আউটপুট
Minimum required flips: 2
