মনে করুন, আমাদের দুটি পূর্ণসংখ্যা x এবং n আছে। আমাদের কাজ হল প্রথম ক্রমাগত ১-গুলোর স্ট্রীম (৩২-বিট বাইনারি) খুঁজে বের করা যাদের দৈর্ঘ্য n-এর চেয়ে বড় বা সমান। এবং তার পজিশন রিটার্ন করা। যদি এমন কোনো স্ট্রিং না থাকে, তবে -1 রিটার্ন করুন। উদাহরণস্বরূপ, যদি x = 35, এবং n = 2 হয়, তবে ফলাফল হবে 31। ৩২-বিট ইন্টিজারে 35-এর বাইনারি রিপ্রেজেন্টেশন হল -
00000000000000000000000000100011। তাই দুটি ক্রমাগত ১ ইনডেক্স 31-এ উপস্থিত, তাই উত্তর 31।
এই সমস্যাটি সমাধানের জন্য, আমাদের লিডিং জিরোর সংখ্যা বের করতে হবে, এবং সেই কাউন্ট থেকে ক্রমাগত ১-গুলো খুঁজে বের করার চেষ্টা করব। ভালোভাবে বুঝতে উদাহরণটি দেখুন।
উদাহরণ
#include <iostream>
using namespace std;
int leadingZeroCount(int x) {
unsigned y;
int n;
n = 32;
for (int i = 16; i > 1; i = i / 2) {
y = x >> i;
if (y != 0) {
n -= i;
x = y;
}
}
y = x >> 1;
if (y != 0)
return n - 2;
return n - x;
}
int consecutiveOnePosition(unsigned x, int n) {
int k, p;
p = 0;
while (x != 0) {
k = leadingZeroCount(x);
x = x << k;
p = p + k;
k = leadingZeroCount(~x);
if (k >= n)
return p + 1;
x = x << k;
p = p + k;
}
return -1;
}
int main() {
int x = 35;
int n = 2;
cout << "Consecutive 1s of length " << n << " is starting from index: " << consecutiveOnePosition(x, n);
}
আউটপুট
Consecutive 1s of length 2 is starting from index: 31
