Problem Statement in English

You’re given a binary array nums. You need to determine for each prefix of the array whether the binary number represented by that prefix is divisible by 5.

Return a list of booleans where the i-th boolean indicates whether the binary number formed by the first i+1 elements of nums is divisible by 5.

Approach

Although there is a method to solve these kind of problems in general, since the questions asks for divisibility by 5 specifically, we can use a more optimized approach. Although I just used the general method here.

The thing about numbers divisible by 5 is that they end with either 0 or 5 in base 10. However, since we are dealing with binary numbers, we can directly compute the decimal value of each prefix and check its divisibility by 5. Mostly, I was just being lazy.

But what we can do is iterate over the input array from left to right, and just left shift the current number by 1 (which is equivalent to multiplying it by 2) and then add the current bit. This way, we can build the binary number incrementally without converting the entire prefix each time.

Solution in Python


class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        curr = 0
        res = []

        for num in nums:            
            curr <<= 1
            curr |= num
            res.append(curr % 5 == 0)

        return res

Complexity

  • Time: $O(n)$
    We iterate through the input list nums once, where n is the length of nums.

  • Space: $O(n)$
    Since we are storing the result for each prefix in a list.

And we are done.