Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Appending a binary digit doubles the previous prefix value and adds the new bit. Thus each prefix can be built from the previous one rather than parsed again. Testing its remainder modulo five determines the corresponding answer.

Approach

Initialize the prefix to zero. For each bit, shift the prefix left by one and combine the new bit with bitwise OR, then append whether the updated value is divisible by five. Return the boolean list in input order. These reference solutions retain the full exact prefix rather than reducing it modulo five after each step; this distinction matters for their big-integer complexity. Leading zeros and the zero prefix are handled naturally.

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

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

        return res

Complexity analysis

Let n = nums.length. Both displayed implementations grow the exact i-bit binary prefix before testing % 5, totaling Theta(n²) bit-operation time and using O(n) bits of auxiliary integer space. This excludes the O(n) returned boolean array.