মান ল করুন একটি num সংখ্যা। ০ ≤ i ≤ num পরিসরে থাকা প্রতিটি i সংখ্যার বাইনারি রিপ্রেজেন্টেশনে ১-এর সংখ্যা গণনা করুন এবং একটি তালিকা হিসেবে ফেরত দিন। যেমন num = 5 হলে, সংখ্যাগুলো হল [0, 1, 2, 3, 4, 5], এবং এদের বাইনরিতে ১-এর সংখ্যা হল [0, 1, 1, 2, 1, 2], তাই মোট হবে ৭।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
res := num + 1 আকারের একটি অ্যারে যা ০ দিয়ে ভরা আছে।
offset := 0
i কে ১ থেকে num + ১ পর্যন্ত লুপ চালান:
যদি i & (i - 1) == 0 হয়, তবে res[i] := 1 এবং offset := 0
অন্যথায় offset ১ বাড়ান এবং res[i] := 1 + res[offset]
res-এর সব উপাদানের যোগফল ফেরত দিন।
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class Solution: def countBits(self, num): result = [0] * (num+1) offset = 0 for i in range(1,num+1): if i & i-1 == 0: result[i] = 1 offset = 0 else: offset+=1 result[i] = 1 + result[offset] return sum(result) ob1 = Solution() print(ob1.countBits(5))
ইনপুট
5
আউটপুট
7
