Binary Prefix Divisible By 5: Running Remainder Pattern

You are given a binary array nums (0-indexed). For each index i, consider the binary number formed by the prefix nums[0..i] (from the most significant bit to the least significant bit). Return a boolean array answer where answer[i] is true if that prefix, interpreted as a binary number, is divisible by 5.

This is LeetCode 1018: Binary Prefix Divisible By 5, an easy problem that teaches a critical trick: you never need to compute the full binary number. Instead, you track only the running remainder modulo 5.

Why this problem matters

At first, this looks like a conversion problem. Read the bits, build a binary number, check if it divides evenly by 5, repeat. But that approach has a hidden trap: the binary number grows with every bit. After 30 bits, you are dealing with numbers in the billions. After 100 bits, you have blown past any standard integer type. The array can have up to 100,000 elements, so the naive approach is not just slow, it is impossible with fixed-width integers.

The real lesson here is modular arithmetic. You do not need the full number to check divisibility. You only need the remainder after dividing by 5. And that remainder can be updated incrementally as each new bit arrives, without ever storing the full value. This is the same principle behind checksums, hash functions, and cyclic redundancy checks in real systems.

Once you see this pattern, you start recognizing it everywhere. Any time a problem asks "is this large number divisible by X?" or "what is the remainder when dividing by X?", you can almost always avoid computing the full number by tracking only the remainder.

The key insight

When you append a new bit to a binary number, the new number equals the old number shifted left by one position, plus the new bit. In mathematical terms: new_value = old_value * 2 + new_bit.

Since you only care about whether the result is divisible by 5, you can take the remainder at each step. Modular arithmetic guarantees that (old_value * 2 + new_bit) % 5 gives the same result as computing the full number and then taking mod 5. This means you can replace old_value with just old_remainder and the math still works:

remainder = (remainder * 2 + bit) % 5

The remainder never exceeds 4, no matter how long the array is. No overflow, no big integer libraries, no extra memory. Just one small number that updates in constant time per bit.

The solution

def prefixes_div_by5(nums: list[int]) -> list[bool]:
    remainder = 0
    result = []
    for bit in nums:
        remainder = (remainder * 2 + bit) % 5
        result.append(remainder == 0)
    return result

Here is what each piece does:

1. Initialize remainder to 0. Before reading any bits, the number is 0, which has remainder 0 when divided by 5.
2. For each bit in the array, update the remainder using the formula (remainder * 2 + bit) % 5. This simulates appending the bit to the binary number without actually building the number.
3. Check if remainder == 0. If so, the current prefix is divisible by 5, and you append True to the result. Otherwise, append False.

Visual walkthrough

Let's trace through nums = [0, 1, 1, 0, 1] step by step, tracking the remainder at each position.

Only the very first prefix (just the bit 0) produces a remainder of 0, so the output is [true, false, false, false, false]. Notice how the remainder stays between 0 and 4 throughout, even though the actual decimal values grow to 13. With 100,000 bits, the decimal value would be astronomically large, but the remainder would still be a single digit.

Complexity analysis

Time: O(n), where n is the length of the input array. You iterate through the array once, performing a constant-time update at each step. The multiplication by 2, the addition, and the modulo operation are all O(1).

Space: O(n) for the output array. If you exclude the output (since the problem requires it), the extra space is O(1), just the single remainder variable.

The building blocks

1. Running modular arithmetic

The pattern of tracking a remainder incrementally instead of computing a full value:

remainder = 0
for element in stream:
    remainder = (remainder * base + element) % modulus

This shows up in hash functions (polynomial rolling hashes use the exact same formula), divisibility checks for large numbers, and checksum algorithms. The key property is that taking the modulus at each step produces the same result as taking it once at the end, but keeps intermediate values small.

2. Bit-by-bit binary construction

The pattern of building a binary number one bit at a time from most significant to least significant:

value = 0
for bit in bits:
    value = value * 2 + bit

This is the standard way to convert a binary representation to decimal. Multiplying by 2 shifts all existing bits left by one position, and adding the new bit fills in the lowest position. You see this in binary-to-decimal converters, bitstream parsers, and anywhere binary data is processed sequentially.

Edge cases

• All zeros nums = [0, 0, 0]: every prefix is 0, which is divisible by 5. The output is all true.
• Single element nums = [1]: the prefix is just 1 (decimal 1), which is not divisible by 5. Output: [false].
• First divisible hit at index 4 nums = [1, 0, 1, 0, 0]: the prefix 10100 is decimal 20, which is divisible by 5. Make sure your loop catches this when the remainder hits 0 after several non-zero steps.
• Very long arrays with up to 100,000 bits: the naive approach of building the full integer fails. The running remainder approach handles this with no issues because the remainder never exceeds 4.
• Alternating bits nums = [1, 0, 1, 0, 1, 0, ...]: the remainder cycles through a predictable pattern. The solution handles this naturally without any special logic.

From understanding to recall

The running remainder formula is one line: remainder = (remainder * 2 + bit) % 5. It is simple enough to memorize, and the reasoning behind it (modular arithmetic preserves divisibility) is something you can re-derive in seconds. But under interview pressure, even simple formulas can slip away if you have not practiced writing them from scratch.

The real challenge is not understanding this problem. It is recognizing the pattern instantly when you see a variation. "Is this huge number divisible by K?" or "check divisibility without computing the full value" are signals that point straight to running modular arithmetic. Spaced repetition drills that recognition until it becomes reflexive. You see the signal, and the formula appears in your mind before you have finished reading the problem.

Related posts

• Subarray Sum Equals K - Another problem where tracking running values with modular arithmetic avoids overflow
• Continuous Subarray Sum - Uses prefix sums with modular arithmetic to check divisibility
• Add Binary - Binary number manipulation that builds intuition for bit-by-bit processing

CodeBricks breaks the binary prefix divisible by 5 problem into its running modular arithmetic and bit-by-bit construction building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a divisibility question shows up in your interview, you do not think about it. You just write it.