# 1018. Binary Prefix Divisible By 5

Given an array `A` of `0`s and `1`s, 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.

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. `1 <= A.length <= 30000`
2. `A[i]` is `0` or `1`

``````class Solution {
public:
vector<bool> prefixesDivBy5(vector<int>& A) {
vector<bool> res;
int cur = 0, n = A.size();
for (int i = 0; i < n; ++i) {
cur = (cur * 2 + A[i]) % 5;
res.push_back(cur % 5 == 0);
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1018

https://leetcode.com/problems/binary-prefix-divisible-by-5/

https://leetcode.com/problems/binary-prefix-divisible-by-5/discuss/265601/Detailed-Explanation-using-Modular-Arithmetic-O(n)

https://leetcode.com/problems/binary-prefix-divisible-by-5/discuss/265554/JavaPython-3-71-liners-left-shift-bitwise-or-and-mod.

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation