Binary Prefix Divisible By 5

main.md

Question

Approach

To solve this, I avoid constructing the full binary number because it grows too fast, so I keep track of only its remainder mod 5. Each time I read a new bit, I update the running value using current = (current * 2 + bit) % 5, which reflects what happens when a bit is appended in binary. If the remainder becomes zero, then the entire prefix forms a number divisible by 5.

Implementation

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

Complexities

• Time: O(n)
• Space: O(n)