1018. Binary Prefix Divisible By 5

问题：

给定一个0，1组成的数组，前 i 个元素组成二进制数，若该二进制数能被5整除，返回true，否则返回false

求出这个数组前 i 个元素（i=0～size()-1）的结果数组。

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=cur*2+A[i]

这个cur会留用到下一次循环中，

如果cur能被5整除，（cur能被5整除->cur*2仍然能被5整除）

那么下一次的cur是否能被5整除，只取决于A[i]

且A[i]%5的余数=下一次的cur%5的余数。

如果cur被5除余cur%5，

那么下一次cur%5的余数=（cur*2+A[i]）%5 = (cur*2%5 + A[i]%5) %5

=  (cur%5*2 + A[i]%5) %5

因此，每次cur可只保留%5的余数，到下一次循环中参与计算。

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& A) {
        int cur=0;
        vector<bool> res;
        for(int a:A){
            cur=(cur*2+a)%5;
            if(!(cur%5)) res.push_back(true);
            else res.push_back(false);
        }
        return res;
    }
};