Problem Description

You are given a binary array nums containing only 0s and 1s, where the array is 0-indexed.

For each position i in the array, we define x_i as the decimal number represented by the binary subarray from index 0 to index i (inclusive). The binary representation reads from left to right, with the leftmost bit being the most significant bit.

For example, if nums = [1,0,1]:

• x_0 = 1 (binary "1" equals decimal 1)
• x_1 = 2 (binary "10" equals decimal 2)
• x_2 = 5 (binary "101" equals decimal 5)

Your task is to return an array of booleans answer where answer[i] is true if x_i is divisible by 5, and false otherwise.

The key insight is that as we traverse the array, each new bit extends the binary number. When we encounter a new bit, the previous number gets shifted left (multiplied by 2) and the new bit is added. To check divisibility by 5, we only need to track the remainder when divided by 5, since (a * 2 + b) % 5 = ((a % 5) * 2 + b) % 5. This optimization prevents integer overflow for large arrays.

Intuition

When we read a binary number from left to right, each new bit we encounter effectively doubles the current value and adds the new bit. For instance, if we have binary "10" (decimal 2) and add a "1", we get "101" which is 2 * 2 + 1 = 5.

The straightforward approach would be to build the complete decimal number at each position and check if it's divisible by 5. However, this could lead to very large numbers that cause overflow issues.

The key observation is that we only care about divisibility by 5, not the actual value. This means we only need to track the remainder when divided by 5. This works because of the modular arithmetic property: (a * 2 + b) % 5 = ((a % 5) * 2 + b) % 5.

Let's trace through an example with nums = [1,0,1]:

• Start with x = 0
• First bit is 1: x = (0 * 2 + 1) % 5 = 1. Since 1 ≠ 0, not divisible by 5
• Second bit is 0: x = (1 * 2 + 0) % 5 = 2. Since 2 ≠ 0, not divisible by 5
• Third bit is 1: x = (2 * 2 + 1) % 5 = 0. Since 0 = 0, divisible by 5

By maintaining only the remainder modulo 5, we avoid overflow and can efficiently determine divisibility. The operation x << 1 | v is a bitwise way to express x * 2 + v, where left shift by 1 doubles the value and OR with v adds the new bit.

Solution Approach

The solution uses a simulation approach with modular arithmetic to efficiently track divisibility by 5.

Implementation Steps:

1. Initialize variables:

   • Create an empty list ans to store the boolean results
   • Initialize x = 0 to represent the current remainder modulo 5

2. Iterate through the binary array: For each bit v in nums:

   • Update x using the formula: x = (x << 1 | v) % 5
     • x << 1 performs a left shift, equivalent to multiplying by 2
     • | v performs a bitwise OR, which adds the current bit (since v is either 0 or 1)
     • % 5 takes the remainder to keep the value bounded
   • Check if x == 0:
     • If true, the current prefix is divisible by 5, append True to ans
     • Otherwise, append False to ans

3. Return the result array

Why this works:

The expression (x << 1 | v) is equivalent to x * 2 + v, which represents adding a new bit to the right of our binary number. By taking modulo 5 at each step, we maintain only the remainder, which is sufficient to determine divisibility.

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the input array, as we iterate through each element once
• Space Complexity: O(1) for the variables (not counting the output array which is O(n))

This approach elegantly avoids potential integer overflow issues that would arise from calculating the full decimal values, especially for large binary arrays.

Example Walkthrough

Let's walk through the solution with nums = [1,1,0,1,1]:

Initial state: x = 0 (remainder), ans = []

Step 1: Process nums[0] = 1

• Calculate: x = (0 << 1 | 1) % 5 = (0 * 2 + 1) % 5 = 1
• Binary so far: "1" = decimal 1
• Is 1 divisible by 5? No (remainder = 1)
• ans = [False]

Step 2: Process nums[1] = 1

• Calculate: x = (1 << 1 | 1) % 5 = (2 + 1) % 5 = 3
• Binary so far: "11" = decimal 3
• Is 3 divisible by 5? No (remainder = 3)
• ans = [False, False]

Step 3: Process nums[2] = 0

• Calculate: x = (3 << 1 | 0) % 5 = (6 + 0) % 5 = 1
• Binary so far: "110" = decimal 6
• Is 6 divisible by 5? No (remainder = 1)
• ans = [False, False, False]

Step 4: Process nums[3] = 1

• Calculate: x = (1 << 1 | 1) % 5 = (2 + 1) % 5 = 3
• Binary so far: "1101" = decimal 13
• Is 13 divisible by 5? No (remainder = 3)
• ans = [False, False, False, False]

Step 5: Process nums[4] = 1

• Calculate: x = (3 << 1 | 1) % 5 = (6 + 1) % 5 = 2
• Binary so far: "11011" = decimal 27
• Is 27 divisible by 5? No (remainder = 2)
• ans = [False, False, False, False, False]

Final Result: [False, False, False, False, False]

Note how we never store the actual decimal values (1, 3, 6, 13, 27) but only track remainders (1, 3, 1, 3, 2), preventing overflow while still determining divisibility by 5.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm iterates through each element in the array exactly once, performing constant-time operations (bit shift, bitwise OR, modulo, and comparison) for each element.

Space Complexity: O(1) if we exclude the space required for the output array ans. The only additional variable used is x, which stores the running remainder and uses constant space regardless of the input size. If we include the output array, the space complexity would be O(n) since the ans array stores n boolean values.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow Without Modular Arithmetic

The Pitfall: A common mistake is trying to compute the full decimal value at each step without using modular arithmetic:

# WRONG APPROACH - Will cause overflow for large arrays
def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
    result = []
    current_value = 0
  
    for bit in nums:
        current_value = current_value * 2 + bit  # No modulo operation!
        result.append(current_value % 5 == 0)
  
    return result

Why it fails: For large binary arrays (e.g., length > 64), the decimal value quickly exceeds integer limits, causing overflow errors or incorrect results.

The Solution: Always apply modulo 5 at each step to keep the value bounded:

current_value = (current_value * 2 + bit) % 5

2. Incorrect Binary Construction

The Pitfall: Some might incorrectly build the binary number by treating it as a string or using wrong bit positioning:

# WRONG - Treating as string concatenation
current_value = int(str(current_value) + str(bit), 2)

# WRONG - Adding bit in wrong position
current_value = current_value + bit * (2 ** position)

The Solution: Use the correct formula that shifts left and adds the new bit:

current_value = (current_value << 1 | bit) % 5
# Or equivalently:
current_value = (current_value * 2 + bit) % 5

3. Forgetting to Handle the Modulo Property

The Pitfall: Only checking divisibility at the end instead of maintaining the modulo throughout:

# WRONG - Only checking modulo at append time
for bit in nums:
    current_value = current_value * 2 + bit
    result.append(current_value % 5 == 0)  # Value grows unbounded

Why it matters: The key insight is that (a * 2 + b) % 5 = ((a % 5) * 2 + b) % 5, which allows us to work with remainders only.

The Solution: Apply modulo 5 immediately after computing the new value to maintain only the remainder throughout the iteration.