# Binary Prefix Divisible By 5
**Difficulty:** EASY
[External](https://leetcode.com/problems/binary-prefix-divisible-by-5)
Canonical: https://scaleengineer.com/dsa/problems/binary-prefix-divisible-by-5
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
You are given a binary array `nums` (**0-indexed**).

We define `xi` as the number whose binary representation is the subarray `nums[0..i]` (from most-significant-bit to least-significant-bit).

* For example, if `nums = [1,0,1]`, then `x0 = 1`, `x1 = 2`, and `x2 = 5`.

Return _an array of booleans_ `answer` _where_ `answer[i]` _is_ `true` _if_ `xi` _is divisible by_ `5`.

**Example 1:**

**Input:** nums = [0,1,1]
**Output:** [true,false,false]
**Explanation:** The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.
Only the first number is divisible by 5, so answer[0] is true.

**Example 2:**

**Input:** nums = [1,1,1]
**Output:** [false,false,false]

**Constraints:**

* `1 <= nums.length <= 105`
* `nums[i]` is either `0` or `1`.

# Approaches
## Brute Force Simulation using BigInteger
This approach directly simulates the process described in the problem. For each prefix of the input array `nums`, we form the corresponding binary number. Since these numbers can become extremely large and exceed the capacity of standard integer types like `long`, we use Java's `BigInteger` class, which can handle arbitrarily large integers. We iterate through the array, build the number for each prefix, and check its divisibility by 5.
**Time:** O(n^2). The loop runs `n` times. Inside the loop, `currentNum` has approximately `i` bits at step `i`. `BigInteger` operations like multiplication and addition take time proportional to the number of bits. So, the `i`-th iteration takes `O(i)` time. The total time is the sum of `O(i)` for `i` from 1 to `n`, which results in `O(n^2)`. · **Space:** O(n). The `BigInteger` `currentNum` can grow to have up to `n` bits, requiring `O(n)` space. The output list `answer` also requires `O(n)` space.
**Pros:** Conceptually straightforward and easy to understand.; Directly translates the problem statement into code.
**Cons:** Inefficient for large inputs. The `O(n^2)` time complexity will lead to a "Time Limit Exceeded" error given the constraint `n <= 10^5`.; High memory usage due to storing the full large number in `BigInteger`.
### Explanation
We initialize an empty list of booleans, `answer`, to store the results. We also initialize a `BigInteger` variable, let's call it `currentNum`, to zero. We iterate through the input array `nums` from left to right. In each step `i`, we update `currentNum` to represent the binary number formed by `nums[0...i]`. The new number is calculated from the previous one by shifting it left by one bit (multiplying by 2) and then adding the current bit `nums[i]`. The formula is `currentNum = currentNum * 2 + nums[i]`. After updating `currentNum`, we check if it's divisible by 5 using the modulo operator. `currentNum.mod(BigInteger.valueOf(5))` will be zero if it is divisible. We append `true` to our `answer` list if it's divisible, and `false` otherwise. After iterating through all the numbers in `nums`, we return the `answer` list. This approach is correct but inefficient for large inputs due to the overhead of `BigInteger` arithmetic.

```java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> answer = new ArrayList<>();
        BigInteger currentNum = BigInteger.ZERO;
        BigInteger five = BigInteger.valueOf(5);
        BigInteger two = BigInteger.valueOf(2);

        for (int bit : nums) {
            // currentNum = currentNum * 2 + bit
            currentNum = currentNum.multiply(two).add(BigInteger.valueOf(bit));
            // Check if currentNum % 5 == 0
            if (currentNum.mod(five).equals(BigInteger.ZERO)) {
                answer.add(true);
            } else {
                answer.add(false);
            }
        }
        return answer;
    }
}
```
### Algorithm
1. Initialize an empty list of booleans, `answer`.
2. Initialize a `BigInteger` variable, `currentNum`, to zero.
3. Iterate through the input array `nums` from left to right.
4. In each step `i`, update `currentNum` to represent the binary number formed by `nums[0...i]`. The new number is calculated from the previous one by shifting it left by one bit (multiplying by 2) and then adding the current bit `nums[i]`. The formula is `currentNum = currentNum * 2 + nums[i]`.
5. After updating `currentNum`, check if it's divisible by 5 using the modulo operator. `currentNum.mod(BigInteger.valueOf(5))` will be zero if it is divisible.
6. Append `true` to the `answer` list if it's divisible, and `false` otherwise.
7. After iterating through all the numbers in `nums`, return the `answer` list.

## Efficient Approach using Modular Arithmetic
A much more efficient approach avoids dealing with large numbers altogether by using modular arithmetic. The key insight is that to check for divisibility by 5, we only need the remainder of the number when divided by 5, not the number itself. We can maintain this remainder as we iterate through the binary array.
**Time:** O(n). We iterate through the input array of length `n` exactly once. Each step inside the loop involves a few constant-time arithmetic operations. · **Space:** O(n). The space is dominated by the output list `answer`, which stores `n` boolean values. The auxiliary space used by the algorithm (for the `remainder` variable) is `O(1)`.
**Pros:** Extremely efficient with linear time complexity.; Constant auxiliary space complexity.; Avoids all issues with large numbers and overflows.
**Cons:** Requires knowledge of modular arithmetic to come up with the solution.
### Explanation
The recurrence relation for the number `x_i` formed by the prefix `nums[0...i]` is `x_i = x_{i-1} * 2 + nums[i]`. We are interested in `x_i % 5`. Using properties of modular arithmetic, we can write: `x_i % 5 = ( (x_{i-1} * 2) + nums[i] ) % 5`. This can be further broken down: `x_i % 5 = ( (x_{i-1} % 5) * 2 + nums[i] ) % 5`. Let `rem_i = x_i % 5`. The formula becomes `rem_i = (rem_{i-1} * 2 + nums[i]) % 5`. This means we can calculate the remainder for the current prefix using only the remainder from the previous prefix. The remainder will always be a small integer (0, 1, 2, 3, or 4), so we can use a standard integer variable to keep track of it, completely avoiding large number arithmetic and potential overflows. The algorithm iterates through the `nums` array, updating the remainder at each step using this formula. If the remainder becomes 0, the number is divisible by 5.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> answer = new ArrayList<>();
        int remainder = 0;
        for (int bit : nums) {
            // Update remainder: remainder = (remainder * 2 + bit) % 5
            // This can be written as a left shift for multiplication by 2
            remainder = ((remainder << 1) | bit) % 5;
            answer.add(remainder == 0);
        }
        return answer;
    }
}
```
### Algorithm
1. Create an empty `List<Boolean>` called `answer`.
2. Initialize an integer `remainder` to 0.
3. Loop through each `bit` in the `nums` array.
4. Update the `remainder` using the formula: `remainder = (remainder * 2 + bit) % 5`.
5. Check if the new `remainder` is 0.
6. Add `true` to `answer` if `remainder` is 0, otherwise add `false`.
7. After the loop, return `answer`.

# Solutions
### Java

```java
class Solution {
public
  List<Boolean> prefixesDivBy5(int[] nums) {
    List<Boolean> ans = new ArrayList<>();
    int x = 0;
    for (int v : nums) {
      x = (x << 1 | v) % 5;
      ans.add(x == 0);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<bool> prefixesDivBy5(vector<int> &nums) {
    vector<bool> ans;
    int x = 0;
    for (int v : nums) {
      x = (x << 1 | v) % 5;
      ans.push_back(x == 0);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]: ans = [] x = 0 for v in nums: x = (x << 1 | v) % 5 ans . append(x == 0) return ans

```