একটি নন-নেগেটিভ সংখ্যা n দেওয়া আছে। এর বাইনারি রিপ্রেজেন্টেশনে সবচেয়ে লম্বা কনsekutিভ 1-এর রানের দৈর্ঘ্য বের করতে হবে।
উদাহরণ: n = 1469 হলে বাইনারি 10110111101। এখানে সর্বোচ্চ ৪টি কনsekutিভ 1 আছে। আউটপুট: 4।
সমাধানের পদ্ধতি
বিট ম্যানিপুলেশন ট্রিক: n = n & (n << 1) অপারেশন প্রতিটি ইটারেশনে প্রতিটি 1-এর রানের দৈর্ঘ্য ১ করে কমিয়ে দেয়। এই অপারেশন কতবার করা যায় তাওই সর্বোচ্চ কনsekutিভ 1-এর দৈর্ঘ্য।
পাইথন কোড
def solve(n):
count = 0
while n != 0:
n = n & (n << 1) # প্রতিটি ১-রান ছোট করুন
count += 1
return count
# টেস্ট
n = 1469
print(solve(n)) # আউটপুট: 4কিভাবে কাজ করে
n = 1469 = 10110111101 (বাইনারি)
- ইটারেশন ১:
n & (n << 1)=1010011100(রান দৈর্ঘ্য ১ কমে) - ইটারেশন ২:
1000011000 - ইটারেশন ৩:
100000000 - ইটারেশন ৪:
0— শূন্য হয়ে গেলে লুপ বন্ধ
মোট ৪ ইটারেশন → সর্বোচ্চ রান দৈর্ঘ্য ৪।
সময় জটিলতা
O(k) যেখানে k = সর্বোচ্চ কনsekutিভ ১-এর দৈর্ঘ্য (সর্বোচ্চ ৬৪ বিটের জন্য ৬৪)। খুব দ্রুত।
