পাইথনে প্রাইম সেট বিট গণনা (Prime Number of Set Bits)

সমস্যা বিবরণ

দুটি পূর্ণসংখ্যা L এবং R দেওয়া থাকে। [L, R] রেঞ্জে কতগুলো সংখ্যার বাইনারি রিপ্রেজেন্টেশনে প্রাইম সংখ্যক সেট বিট (১) আছে তা গণনা করুন।

উদাহরণ

L = 6, R = 10 → আউটপুট: 4

সংখ্যাগুলো: 6(110→2), 7(111→3), 8(1000→1), 9(1001→2), 10(1010→2)। প্রাইম সেট বিট যেগুলো: 6,7,9,10 → মোট ৪টি।

এলগরিদম

1. প্রাইম সংখ্যা (২০ পর্যন্ত): [2,3,5,7,11,13,17,19]।
2. count = 0।
3. j = L থেকে R পর্যন্ত লুপ:
   • popcount = bin(j).count('1')।
   • যদি popcount প্রাইম লিস্টে থাকে → count++।
4. count রিটার্ন করুন।

পাইথন বাস্তবায়ন

class Solution:
    def countPrimeSetBits(self, L, R):
        primes = {2,3,5,7,11,13,17,19}
        def popcount(x):
            return bin(x).count('1')
        count = 0
        for j in range(L, R+1):
            if popcount(j) in primes:
                count += 1
        return count

ob = Solution()
print(ob.countPrimeSetBits(6, 10))  # 4

ইনপুট / আউটপুট

ইনপুট: 6, 10
আউটপুট: 4