题目描述

给定一个包含 0 和 1 的数组 A。考虑 N_i：表示从 A[0] 到 A[i] 的第 i 个子数组，且代表一个二进制数（从最高位到最低位）。

返回一个布尔型数组，其中 answer[i] 为 true 当且仅当 N_i 能被 5 整除。

样例

输入：[0,1,1]
输出：[true,false,false]
解释：
输入的数字以二进制表示为 0, 01, 011; 十进制表示为 0, 1 和 3。仅有第一个数字能被 5 整除，所以 answer[0] 是 true。

输入：[1,1,1]
输出：[false,false,false]

输入：[0,1,1,1,1,1]
输出：[true,false,false,false,true,false]

输入：[1,1,1,0,1]
输出：[false,false,false,false,false]

注意

• 1 <= A.length <= 30000
• A[i] is 0 or 1

算法

(模拟) $O(n)$

1. 根据题意，我们维护一个变量表示当前数字模 5 之后的余数。
2. 从头开始遍历数组，初始时这个余数是 0，每次乘 2 之后加上当前数字再模 5。

时间复杂度

• 仅遍历一次数组，故时间复杂度为 $O(n)$。

空间复杂度

• 额外数组保存答案，故空间复杂度为 $O(n)$。

C++ 代码

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