একটি সংখ্যা n দেওয়া আছে। ১ থেকে n পর্যন্ত কতগুলো ইন্টিজারের বাইনারি রিপ্রেজেন্টেশনে অড্ড সংখ্যক সেট বিট (১) আছে, তা বের করতে হবে।
উদাহরণ: n=10 হলে আউটপুট ৫। (১,২,৩,৪,৫,৬,৭,৮,৯,১০-র মধ্যে ৫টির বাইনারি-তে অড্ড সংখ্যক ১ আছে)।
অ্যালগরিদম
- getSetBitsCount(n): while(n) { if(n%2==1) count++; n/=2; }
- getOddSetBitsIntegerCount(n): ১ থেকে n পর্যন্ত লুপ, সেট বিট অড্ড হলে count++
ইমপ্লিমেন্টেশন
#include <bits/stdc++.h> using namespace std; int getSetBitsCount(int n) { int count = 0; while (n) { if (n % 2 == 1) count += 1; n /= 2; } return count; } int getOddSetBitsIntegerCount(int n) { int count = 0; for (int i = 1; i <= n; i++) { if (getSetBitsCount(i) % 2 == 1) count += 1; } return count; } int main() { int n = 10; cout << getOddSetBitsIntegerCount(n) << endl; return 0; }আউটপুট
5
