Binary Prefix Divisible By 5

The key to this problem is understanding how to build up the binary representation incrementally, which is analogous to calculating the value of a number in base-10 from its digit representation.

Here is how we can approach this problem:

  1. Initialize a variable, say num, to 0. This variable will store the running value of the binary number as we traverse the nums array.

  2. Create a list res to store the boolean results.

  3. For each bit in nums, we shift the current value of num to the left (which is equivalent to multiplying num by 2 in decimal) and then add the current bit. This operation will construct the number xi bit by bit.

  4. Check if the current number num is divisible by 5. If it is, append True to res, otherwise append False.

  5. Since num can grow large due to left shift, and we only care about whether it’s divisible by 5, we can take a modulus by 5 at each step to keep num manageable.

Python solution:

1
2
3
4
5
6
7
8

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        num = 0
        res = []
        for i in nums:
            num = ((num << 1) + i) % 5
            res.append(num == 0)
        return res

In this code, we iterate over the input list nums and build up the number num bit by bit. The expression (num << 1) + i calculates the current value of num, and the modulus operator % 5 ensures that num doesn’t grow too large. The result of the divisibility test num == 0 is appended to the res list. The function returns the res list, which is the desired output.