সমস্যা বিবরণ
একটি সংখ্যা n দেওয়া আছে, কাজ হল প্রদত্ত n-এর বাইনারি রিপ্রেজেন্টেশনে দুটি তাৎক্ষণিক ১-এর মধ্যে সর্বোচ্চ ০ এর সংখ্যা বের করা। যদি বাইনারি রিপ্রেজেন্টেশনে দুইটির কম ১ থাকে তবে -1 রিটার্ন করুন।
উদাহরণ
যদি ইনপুট নম্বর হয় 35 তবে এর বাইনারি রিপ্রেজেন্টেশন হল:
00100011
উপরোক্ত বাইনারি রিপ্রেজেন্টেশনে দুটি তাৎক্ষণিক ১-এর মধ্যে ৩টি ০ আছে। তাই উত্তর ৩।
অ্যালগরিদম
এই সমস্যা সমাধানের জন্য বিটওয়াইজ শিফট অপারেটর ব্যবহার করা যায়। n-এর বাইনারি রিপ্রেজেন্টেশনে দুটি তাৎক্ষণিক ১-এর পজিশন খুঁজে বের করে তাদের পার্থক্য maksimize করতে হবে।
- যদি সংখ্যা ০ হয় বা ২-এর ঘাত হয় তবে -1 রিটার্ন করুন।
- prev ভেরিয়েবল আরম্ভ করুন প্রথম রাইটমোস্ট ১-এর পজিশনে। এটি পূর্বে দেখা ১-এর পজিশন সংরক্ষণ করে।
- cur নামক অন্য একটি ভেরিয়েবল নিন যা prev-এর ঠিক পরের ১-এর পজিশন সংরক্ষণ করে।
- cur - prev - 1 এর পার্থক্য নিন, এটি দুটি তাৎক্ষণিক ১-এর মধ্যে ০-এর সংখ্যা হবে এবং এটি পূর্বের ০-এর সর্বোচ্চ মান থেকে তুলনা করুন এবং prev আপডেট করুন (prev = cur) পরবর্তী ইটারেশনের জন্য।
- setBit ভেরিয়েবল ব্যবহার করুন, যা n-এর সব বিট স্ক্যান করে এবং বর্তমান বিট ০ নাকি ১ সেটা ডিটেক্ট করতে সাহায্য করে।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMaxZeros(int n) {
if (n == 0 || (n & (n - 1) == 0)) {
return -1;
}
int setBit = 1;
int prev = 0;
int i;
for (i = 1; i < sizeof(int) * 8; ++i) {
++prev;
if ((n & setBit) == setBit) {
setBit = setBit << 1;
break;
}
setBit = setBit << 1;
}
int maxZeros = INT_MIN;
int cur = prev;
for (int j = i + 1; j <= sizeof(int) * 8; ++j) {
++cur;
if ((n & setBit) == setBit) {
if (maxZeros < (cur - prev - 1)) {
maxZeros = cur - prev - 1;
prev = cur;
}
}
setBit = setBit << 1;
}
return maxZeros;
}
int main() {
int n = 35;
cout << "Maximum zeros = " << getMaxZeros(n) << endl;
return 0;
}
আউটপুট
Maximum zeros = 3
