C++-এ সংখ্যার বাইনারি রিপ্রেজেন্টেশনে দীর্ঘতম ক্রমাগত ১-এর রান বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি সংখ্যা n দেওয়া থাকলে, এর বাইনারি রিপ্রেজেন্টেশনে দীর্ঘতম ক্রমাগত ১ (consecutive 1s) এর দৈর্ঘ্য বের করতে হবে।

উদাহরণ: n = 312 হলে বাইনারি = 100111000, যেখানে সর্বোচ্চ ৩টি ক্রমাগত ১ আছে। আউটপুট: ৩।

সমাধানের পদ্ধতি

1. ret = 0, len = 0 ইনিশিয়ালাইজ করুন।
2. ৩২ বিটের জন্য লুপ চালান (i = 0 থেকে 31)।
3. প্রতি বিটের জন্য: if ((n >> i) & 1) চেক করুন।
   • যদি ১ হয়: len++
   • অন্যথায়: len = 0
4. ret = max(ret, len) আপডেট করুন।
5. শেষে ret রিটার্ন করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(int n) {
        int ret = 0;
        int len = 0;
        for (int i = 0; i < 32; i++) {
            if ((n >> i) & 1) {
                len++;
            } else {
                len = 0;
            }
            ret = max(ret, len);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.solve(312);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: 312

আউটপুট: 3

বিকল্প পদ্ধতি (ব্রায়ান কার্নিঘ্যান অ্যালগরিদম)

n = n & (n << 1) অপারেশনটি প্রতিবার শেষের ক্রমাগত ১-র দৈর্ঘ্য ১ করে কমায়। এই অপারেশন কতবার করা যায় সেটি কাউন্ট করলেই উত্তর পাওয়া যায়। এটি O(k) সময় নেয়, যেখানে k = ক্রমাগত ১-এর দৈর্ঘ্য।

জটিলতা

• সময়: O(32) = O(1)
• স্থান: O(1)