রেঞ্জ [0, n]-এ শুধু এক সেট বিট সংখ্যা গণনা C++-এ

০ থেকে n পর্যন্ত কতটি সংখ্যার বাইনারি রিপ্রেজেন্টেশনে ঠিক একটি সেট বিট (১) আছে তা বের করতে হবে। এই সংখ্যাগুলো হলো ২-এর ঘাতাবলী: ১, ২, ৪, ৮, ১৬, ...

উদাহরণ

n = 15

সেট বিট ১ olan সংখ্যা: ১ (১), ২ (১০), ৪ (১০০), ৮ (১০০০) → মোট 4টি

অ্যালগরিদম

1. সাধারণ: ১ থেকে n পর্যন্ত লুপ চালিয়ে __builtin_popcount(i) == 1 চেক করুন।
2. দক্ষ: ১ থেকে শুরু করে ২ দিয়ে গুণ করুন যতক্ষণ ≤ n। কাউন্ট করুন। O(log n) সময়।

C++ কোড উদাহরণ (দুই পদ্ধতি)

#include <iostream>
using namespace std;

// Naive approach
int countOneSetBitNaive(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++)
        if (__builtin_popcount(i) == 1) count++;
    return count;
}

// Efficient approach
int countOneSetBitEfficient(int n) {
    int count = 0;
    for (long long p = 1; p <= n; p *= 2)
        count++;
    return count;
}

int main() {
    int n = 15;
    cout << "Naive: " << countOneSetBitNaive(n) << endl;
    cout << "Efficient: " << countOneSetBitEfficient(n);
    return 0;
}

ইনপুট

15

আউটপুট

4