LeetCode 1018: Binary Prefix Divisible By 5

Problem Restatement

We are given a binary array nums.

For each index i, consider the binary number formed by nums[0], nums[1], ..., nums[i].

We need to return a boolean array answer where answer[i] is true if the binary number formed by the prefix nums[0:i+1] is divisible by 5.

The official constraints state that 1 <= nums.length <= 10^5 and nums[i] is either 0 or 1.

Input and Output

Function shape:

def prefixesDivBy5(nums: list[int]) -> list[bool]:
    ...

Examples

Example 1:

nums = [0, 1, 1]

Prefixes:

Answer:

[True, False, False]

Example 2:

nums = [1, 1, 1]

Answer:

[False, False, False]

Key Insight

We do not need to store the full prefix number (it can be astronomically large).

Only the remainder modulo 5 matters for divisibility.

When we extend the prefix by one bit b, the new number is:

new_value = old_value * 2 + b
new_remainder = (old_remainder * 2 + b) % 5

Track only this remainder.

Algorithm

1. Initialize remainder = 0.
2. For each bit b in nums:
   • remainder = (remainder * 2 + b) % 5.
   • Append remainder == 0 to the result.
3. Return the result.

Correctness

At each step, remainder holds the value of the prefix number modulo 5.

The recurrence (remainder * 2 + b) % 5 correctly updates the remainder when appending a new bit.

If remainder == 0, the current prefix number is divisible by 5.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def prefixesDivBy5(self, nums: list[int]) -> list[bool]:
        result = []
        remainder = 0

        for bit in nums:
            remainder = (remainder * 2 + bit) % 5
            result.append(remainder == 0)

        return result

Code Explanation

Track the running remainder:

remainder = (remainder * 2 + bit) % 5

Multiplying by 2 shifts the binary number left by one bit, and adding bit appends the new bit.

The modulo ensures we never deal with large numbers.

Append the result for the current prefix:

result.append(remainder == 0)

Testing

def run_tests():
    s = Solution()

    assert s.prefixesDivBy5([0, 1, 1]) == [True, False, False]
    assert s.prefixesDivBy5([1, 1, 1]) == [False, False, False]
    assert s.prefixesDivBy5([0]) == [True]
    assert s.prefixesDivBy5([1, 0, 1, 0, 1]) == [False, False, False, False, True]

    print("all tests passed")

run_tests()