সমস্যা বিবৃতি
একটি সংখ্যা n দেওয়া হয়েছে, কাজটি হল প্রদত্ত n-এর বাইনারি উপস্থাপনায় দুটি অবিলম্বে 1 এর মধ্যে সর্বাধিক 0’s বের করা। রিটার্ন -1 যদি বাইনারি উপস্থাপনায় দুটি 1’র কম থাকে
উদাহরণ
যদি ইনপুট সংখ্যা 35 হয় তবে এর বাইনারি উপস্থাপনা হল −
00100011
উপরের বাইনারি উপস্থাপনায় দুটি তাৎক্ষণিক 1 এর মধ্যে 3 0 আছে। তাই উত্তর হল 3.
অ্যালগরিদম
এই সমস্যা সমাধানের জন্য আমরা বিটওয়াইজ শিফট অপারেটর ব্যবহার করতে পারি। আমাদের n এর বাইনারি উপস্থাপনায় দুটি অবিলম্বে 1 এর অবস্থান খুঁজে বের করতে হবে এবং এই অবস্থানের পার্থক্যকে সর্বাধিক করতে হবে।
- যদি সংখ্যা 0 বা 2 এর শক্তি হয় তাহলে -1 ফেরত দিন
- প্রথম ডান সর্বাধিক 1 এর অবস্থান সহ ভেরিয়েবল পূর্ববর্তী শুরু করুন। এটি পূর্বে দেখা 1 এর অবস্থান সংরক্ষণ করে।
- আরেকটি ভেরিয়েবল কার নিন যা পূর্বের ঠিক পরে অবিলম্বে 1 এর অবস্থান সংরক্ষণ করে।
- কার - আগের - 1 এর পার্থক্য নিন, এটি অবিলম্বে 1 এর মধ্যে 0 এর সংখ্যা হবে এবং এটি 0 এর পূর্ববর্তী সর্বোচ্চ মানের সাথে তুলনা করুন এবং আগের আপডেট করুন; পরবর্তী পুনরাবৃত্তির জন্য prev=cur।
- ভেরিয়েবল সেটবিট ব্যবহার করুন, যা n-এর সমস্ত বিট স্ক্যান করে এবং বর্তমান বিট 0 বা 1 কিনা তা সনাক্ত করতে সহায়তা করে। সহায়ক ভেরিয়েবল সেটবিট ব্যবহার করুন, যা n-এর সমস্ত বিট স্ক্যান করে এবং বর্তমান বিট 0 বা 1 কিনা তা সনাক্ত করতে সহায়তা করে। li>
উদাহরণ
আসুন এখন একটি উদাহরণ দেখি -
#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
