Chương trình đếm tổng số bit tập hợp của tất cả các số trong phạm vi từ 0 đến n bằng Python

Giả sử chúng ta có một số num. Đối với mỗi số i trong phạm vi 0 ≤ i ≤ num, chúng ta phải tính số 1 trong bản sao nhị phân của chúng và trả về chúng dưới dạng danh sách. Vì vậy, nếu số là 5, thì các số là [0, 1, 2, 3, 4, 5] và số 1 trong các số này là [0, 1, 1, 2, 1, 2], vì vậy nó sẽ trả lại 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• res:=một mảng chứa num + 1 số 0

• bù đắp:=0

• cho tôi trong phạm vi từ 1 đến num + 1

  • nếu tôi và i - 1 =0, thì res [i]:=1 và offset:=0

  • khác tăng độ lệch lên 1 và res [i]:=1 + res [offset]

• trả về tổng các phần tử của res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

5

Đầu ra

7