একটি পূর্ণসংখ্যা n দেওয়া আছে। এর বাইনারি রিপ্রেজেন্টেশনে শুধু একটি 0 কে 1 ফ্লিপ করে সর্বোচ্চ দৈর্ঘ্যের ১ সিকোয়েন্স বের করুন। উদাহরণ: 13 (1101) -> 0 কে 1 করলে 1111 (দৈর্ঘ্য ৪)।
বিট ট্রাভার্স করে করেন্ট এবং প্রিভিয়াস ১ সিকোয়েন্স লেন্থ ট্র্যাক করুন।
উদাহরণ
#include <iostream>
#include <algorithm>
using namespace std;
int singleFlipMaxOnes(unsigned num) {
if (~num == 0) return 8*sizeof(int);
int curr = 0, prev = 0, max_len = 0;
while (num) {
if (num & 1) curr++;
else {
prev = (num & 2) ? curr : 0;
curr = 0;
}
max_len = max(max_len, prev + curr);
num >>= 1;
}
return max_len + 1;
}
int main() {
cout << "Max length of 1s with one flip: " << singleFlipMaxOnes(13);
return 0;
}
আউটপুট
Max length of 1s with one flip: 4
