C++ প্রোগ্রামে বাউম-সুইট (Baum-Sweet) সিকোয়েন্সের n-তম টার্ম বের করা

ভূমিকা

বাউম-সুইট সিকোয়েন্স একটি বাইনারি সিকোয়েন্স। n-তম টার্ম ১ হবে যদি n-এর বাইনারি রিপ্রেজেন্টেশনে কোনো ধারাবাহিক ০ (contiguous zeros) বিজোড় দৈর্ঘ্যের না থাকে। অন্যথায় ০ হবে।

উদাহরণ

n = 4 → বাইনারি: 100 → দুটি ধারাবাহিক ০ (জোড়) → আউটপুট: 1
n = 5 → বাইনারি: 101 → একটি ০ (বিজোড়) → আউটপুট: 0

C++ প্রোগ্রাম উদাহরণ

#include 
using namespace std;

int BaumSweetSeqTerm(int n) {
    bitset<32> bits(n);
    int len = 32 - __builtin_clz(n); // প্রথম ১-এর আগের ০ গুলো বাদ দিন
    int baum = 1;
    for (int i = 0; i < len; ) {
        if (bits[i] == 0) {
            int count = 1, j = i+1;
            while (j < len && bits[j] == 0) { count++; j++; }
            if (count % 2 == 1) baum = 0;
            i = j;
        } else i++;
    }
    return baum;
}

int main() {
    cout << BaumSweetSeqTerm(4); // 1
    return 0;
}