Binary Prefix Divisible By 5

Difficulty: Easy | Acceptance: 53.70% | Paid: No Topics: Array, Bit Manipulation

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).

Return an array answer where answer[i] is true if xi is divisible by 5.

• Examples
• Constraints
• Modulo Arithmetic
• Finite State Machine

Examples

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 <= 10⁴
0 <= nums[i] <= 1

Modulo Arithmetic

Intuition The binary number grows exponentially, potentially exceeding the storage capacity of standard integer types (e.g., 32-bit or 64-bit integers). However, we only need to know if the number is divisible by 5. We can use the property of modular arithmetic: $(a + b) % m = ((a % m) + (b % m)) % m$. When we append a bit $b$ to a number $x$, the new number is $2x + b$. Therefore, we can maintain the remainder modulo 5 at each step.

Steps

• Initialize a variable remainder to 0.
• Iterate through each bit in the input array.
• Update the remainder using the formula: remainder = (remainder * 2 + current_bit) % 5.
• If the updated remainder is 0, append true to the result list; otherwise, append false.
• Return the result list.

from typing import List

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        ans = []
        remainder = 0
        for num in nums:
            remainder = (remainder * 2 + num) % 5
            ans.append(remainder == 0)
        return ans

Complexity

• Time: O(n), where n is the length of the array. We process each element exactly once.
• Space: O(1), excluding the space required for the output array. We only use a single integer variable to track the remainder.
• Notes: This approach avoids integer overflow by applying the modulo operation at every step.

Finite State Machine

Intuition Since we are only interested in the remainder modulo 5, the possible remainders are limited to the set 4. We can model the transitions between these states based on the next bit (0 or 1). This creates a Finite State Machine (FSM) where each state represents the current remainder, and edges represent the operation of appending a bit.

Steps

• Define a transition map or logic that determines the next state (remainder) given the current state and the input bit.
• Start with an initial state of 0.
• Iterate through the binary array, updating the state according to the transition rules.
• Check if the current state is 0 to determine divisibility.

from typing import List

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        # Transitions[state][bit] = next_state
        transitions = {
            0: {0: 0, 1: 1},
            1: {0: 2, 1: 3},
            2: {0: 4, 1: 0},
            3: {0: 1, 1: 2},
            4: {0: 3, 1: 4}
        }
        ans = []
        state = 0
        for num in nums:
            state = transitions[state][num]
            ans.append(state == 0)
        return ans

Complexity

• Time: O(n), as we traverse the array once.
• Space: O(1), as the number of states is constant (5).
• Notes: This approach is conceptually equivalent to the Modulo Arithmetic approach but frames the solution in terms of state transitions, which is useful for hardware design or more complex sequence validation.