# 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

| Item | Meaning |
|---|---|
| Input | Binary array `nums` |
| Output | Boolean array: `true` if the prefix integer is divisible by `5` |

Function shape:

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

## Examples

Example 1:

```python
nums = [0, 1, 1]
```

Prefixes:

| Prefix | Binary | Decimal | Divisible by 5? |
|---|---|---:|---|
| `[0]` | `"0"` | `0` | Yes |
| `[0,1]` | `"01"` | `1` | No |
| `[0,1,1]` | `"011"` | `3` | No |

Answer:

```python
[True, False, False]
```

Example 2:

```python
nums = [1, 1, 1]
```

| Prefix | Binary | Decimal | Divisible by 5? |
|---|---|---:|---|
| `[1]` | `"1"` | `1` | No |
| `[1,1]` | `"11"` | `3` | No |
| `[1,1,1]` | `"111"` | `7` | No |

Answer:

```python
[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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Single pass |
| Space | `O(1)` | Only one variable besides the output |

## 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

```python
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:

```python
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:

```python
result.append(remainder == 0)
```

## Testing

```python
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()
```

| Test | Expected | Why |
|---|---|---|
| `[0,1,1]` | `[T,F,F]` | Prefix `0` is divisible, others are not |
| `[1,1,1]` | `[F,F,F]` | None are divisible |
| `[0]` | `[T]` | `0 % 5 == 0` |
| `[1,0,1,0,1]` | `[F,F,T,T,F]` | Prefix values are `1, 2, 5, 10, 21`; only `5` and `10` are divisible by `5` |