Code Implementation

class Solution:
    def prefixesDivBy5(self, A):
        result = []
        num = 0
        for bit in A:
            num = ((num << 1) + bit) % 5
            result.append(num == 0)
        return result
      

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& A) {
        vector<bool> result;
        int num = 0;
        for (int bit : A) {
            num = ((num << 1) + bit) % 5;
            result.push_back(num == 0);
        }
        return result;
    }
};
      

class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        List<Boolean> result = new ArrayList<>();
        int num = 0;
        for (int bit : A) {
            num = ((num << 1) + bit) % 5;
            result.add(num == 0);
        }
        return result;
    }
}
      

var prefixesDivBy5 = function(A) {
    let result = [];
    let num = 0;
    for (let bit of A) {
        num = ((num << 1) + bit) % 5;
        result.push(num === 0);
    }
    return result;
};
      

Problem Description

Given an array A of 0s and 1s, each representing a single bit of a binary number, you are to return a list of booleans. For each prefix of the array (from the start up to each index), determine whether the binary number represented by that prefix is divisible by 5. The output list should have the same length as A, where each element at index i is True if the binary number formed by A[0] to A[i] is divisible by 5, otherwise False.

Constraints:

• Each element of A is either 0 or 1.
• The length of A is between 1 and 30000.

Thought Process

At first glance, the problem seems to ask for repeated conversion of binary arrays to integers, and then checking divisibility by 5. However, converting each prefix to an integer for every index would be inefficient, especially for long arrays. We need a way to efficiently update our calculation as we extend the prefix by one bit at each step.

The key insight is that we can build the current number incrementally as we process each bit, using the mathematical property of binary numbers: appending a bit to a binary number is equivalent to multiplying the current number by 2 and adding the new bit. We can also use modular arithmetic to keep the number manageable, since we only care about divisibility by 5.

Solution Approach

We will process the input array A from left to right, maintaining a running total representing the current prefix as a binary number, but always keeping it modulo 5. This ensures that the numbers never get too large, and we can quickly check divisibility.

• Initialize a variable num to 0. This will store our running binary number modulo 5.
• Iterate over each bit in A:
• Update num as num = (num * 2 + bit) % 5.
• Append True to the result list if num is 0 (divisible by 5), else False.
• Return the result list after processing all bits.

This approach is efficient because:

• We never store or compute the full integer value for large prefixes.
• Modulo 5 keeps our running value small (always between 0 and 4).
• The algorithm is linear in time and space.

Example Walkthrough

Let's take A = [1, 0, 1, 1, 1, 0, 0, 1, 0].

• Start with num = 0.
• Step 1: bit=1 → num = (0*2+1) % 5 = 1 → False
• Step 2: bit=0 → num = (1*2+0) % 5 = 2 → False
• Step 3: bit=1 → num = (2*2+1) % 5 = 0 → True
• Step 4: bit=1 → num = (0*2+1) % 5 = 1 → False
• Step 5: bit=1 → num = (1*2+1) % 5 = 3 → False
• Step 6: bit=0 → num = (3*2+0) % 5 = 1 → False
• Step 7: bit=0 → num = (1*2+0) % 5 = 2 → False
• Step 8: bit=1 → num = (2*2+1) % 5 = 0 → True
• Step 9: bit=0 → num = (0*2+0) % 5 = 0 → True

So the output is [False, False, True, False, False, False, False, True, True].

Time and Space Complexity

• Brute-force approach: For each prefix, convert the binary number to decimal and check divisibility. This takes O(N^2) time and O(N) space, since each conversion could take O(N) time for N bits.
• Optimized approach (this solution): We process each bit once, and each operation (modulo and addition) is O(1), so the total time complexity is O(N), where N is the length of A. The space complexity is also O(N), for the result array.

Summary

The problem is elegantly solved using modular arithmetic, building the binary number incrementally and always working modulo 5. This avoids large integer computations and makes the solution efficient and concise. The key insight is that for divisibility, we only need to track the remainder, not the entire number, making the solution both fast and memory efficient.