Binary Prefix Divisible By 5

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

The key insight here is that we don’t need to store the full binary number. We only care about divisibility by 5, so we can work with remainders.

When we shift left by one bit and add a new digit, we multiply the current value by 2 and add the new bit. To keep the number small, we take the remainder when divided by 5 at each step.

vector<bool> prefixesDivBy5(vector<int>& A) {
    int len=A.size();
    int n=A[0];
    vector<bool> res(len, false);
    if (n==0) res[0]=true;
    for(int i=1;i<len;++i) {
        n=(n<<1)|A[i];
        n%=5;	// we only care about the remainder
        res[i]=!n;
    }
    return res;
}

The algorithm runs in O(n) time and O(1) extra space (not counting the result array). The bit shifting (n<<1) multiplies by 2, then we OR with the new bit. Taking n%5 keeps our number small while preserving the divisibility property we care about.