Tiền tố nhị phân chia hết cho 5 trong Python

Giả sử ta có mảng A gồm 0 và 1, coi N[i] là mảng con thứ i từ chỉ số A[0] đến A[i] hiểu là số nhị phân. Ta phải tìm list câu trả lời boolean, trong đó answer[i] là true khi và chỉ khi N[i] chia hết cho 5.

Ví dụ, nếu đầu vào là [0,1,1,1,1,1], đầu ra sẽ là [true,false,false,false,true,false]

Để giải quyết, ta làm theo các bước:

• length := kích thước A
• ans := mảng kích thước length, điền false
• number := giá trị nhị phân bằng cách nối các phần tử từ A
• for i in range 0 to length, do
  • if number mod 5 == 0, then
    • ans[length-i-1] := True
  • number := number / 2
• return ans

Xem triển khai sau để hiểu rõ hơn:

Ví dụ

class Solution:
    def prefixesDivBy5(self, A):
        length = len(A)
        ans = [False] * length
        number = int("".join(map(str, A)), 2)
        for i in range(length):
            if number % 5 == 0:
                ans[length - i - 1] = True
            number = number >> 1
        return ans
ob = Solution()
print(ob.prefixesDivBy5([0,1,1,1,1,1]))

Đầu vào

[0,1,1,1,1,1]

Đầu ra

[True, False, False, False, True, False]