Description
Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)
Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.
给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。
返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。
题目链接：https://leetcode.com/problems/binary-prefix-divisible-by-5/
Difficulty: medium
Example 1:
Input: [0,1,1]
Output: [true,false,false]
Explanation:
The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10. Only the first number is divisible by 5, so answer[0] is true.
Example 2:
Input: [1,1,1]
Output: [false,false,false]
Example 3:
Input: [0,1,1,1,1,1]
Output: [true,false,false,false,true,false]
Example 4:
Input: [1,1,1,0,1]
Output: [false,false,false,false,false]
Note:
- 1 <= A.length <= 30000
- A[i] is 0 or 1
分析
- cur记录当前二进制表示的数值，初始为0，ans记录cur能否整除5；
- 遍历A，cur=cur*2+a，若cur可以整除5，ans增加True，反之False；
- 返回ans，时间复杂度为 $O(logN)$。
参考代码
class Solution(object):
def prefixesDivBy5(self, A):
ans=[]
cur=0
for a in A:
cur=cur*2+a
if(cur%5==0):
ans.append(True)
else:
ans.append(False)
return ans