ধরুন আমাদের একটি পূর্ণসংখ্যা n আছে। এর ভিতরে, আমরা 1s-এর দীর্ঘতম ক্রম তৈরি করতে এক-বিট ফ্লিপ করতে পারি। ধরুন সংখ্যাটি 13, তাই বাইনারি উপস্থাপনা হল 1101৷ যদি আমরা 0 থেকে 1 মেক হিসাবে এক-বিট ফ্লিপ করি তবে এটি 1111 হবে৷ এটি 1s এর দীর্ঘতম ক্রম
এই সমস্যাটি সমাধান করার জন্য, আমরা একটি প্রদত্ত সংখ্যার বিটগুলির মধ্য দিয়ে হাঁটব। আমরা বর্তমান 1 এর ক্রম দৈর্ঘ্য এবং পূর্ববর্তী 1 এর ক্রম দৈর্ঘ্য ট্র্যাক রাখব। যখন একটি শূন্য পাওয়া যায়, তারপর পূর্ববর্তী দৈর্ঘ্য আপডেট করুন। তাই পরের বিট যদি 1 হয়, তাহলে আগের দৈর্ঘ্য বর্তমান দৈর্ঘ্য সেট করা উচিত। যদি পরেরটি 0 হয়, তাহলে আগেরটিকে আবার 0 হিসাবে করুন।
উদাহরণ
#include<iostream>
using namespace std;
int singleFlipMaxOnes(unsigned number) {
if (~number == 0)
return 8*sizeof(int);
int curr = 0, prev = 0, max_size = 0;
while (number!= 0) {
if ((number & 1) == 1)
curr++;
else if ((number & 1) == 0) {
prev = (number & 2) == 0? 0 : curr;
curr = 0;
}
max_size = max(prev + curr, max_size);
number >>= 1;
}
return max_size+1;
}
int main() {
cout << "Maximum length of the sequence with 1s: " << singleFlipMaxOnes(13);
} আউটপুট
Maximum length of the sequence with 1s: 4
