โปรแกรมนับจำนวนบิต 1 ทั้งหมดของตัวเลขในช่วง 0 ถึง n ด้วย Python

สมมติว่าเรามีตัวเลข num สำหรับแต่ละตัวเลข i ในช่วง 0 ≤ i ≤ num เราต้องคำนวณจำนวนบิต 1 ในตัวแทนบाइनารีของมัน และคืนค่าผลรวมทั้งหมด

ตัวอย่าง: ถ้า num = 5 ตัวเลขคือ [0, 1, 2, 3, 4, 5] จำนวนบิต 1 คือ [0, 1, 1, 2, 1, 2] ผลรวมคือ 7

ขั้นตอนการแก้ปัญหา

1. สร้างอาร์เรย์ result ขนาด num + 1 เติมด้วย 0
2. กำหนด offset = 0
3. วนลูป i จาก 1 ถึง num:
   • ถ้า i & (i - 1) == 0 (เป็นกำลังของ 2) ให้ result[i] = 1 และ offset = 0
   • อื่นๆ เพิ่ม offset ขึ้น 1 และ result[i] = 1 + result[offset]
4. คืนค่าผลรวมของอิลิเมนต์ใน result

ตัวอย่างโค้ด Python

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))  # Output: 7

อินพุต / เอาต์พุต

Input: 5

Output: 7