LeetCode 1018 - Binary Prefix Divisible By 5

LeetCode Problem 1018

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem presents a binary array nums, where each element is either 0 or 1. We are asked to compute the sequence of numbers formed by interpreting the subarray nums[0..i] as a binary number, denoted as xi. The task is to return a boolean array indicating, for each i, whether xi is divisible by 5.

In simpler terms, starting from the first element of the array, we treat the growing prefix as a binary number, convert it to decimal, and check divisibility by 5. For example, given nums = [1,0,1], the prefixes are [1], [1,0], [1,0,1], which correspond to decimal values 1, 2, and 5. The output would then indicate whether each decimal value is divisible by 5: [False, False, True].

The input constraints tell us that the array can be very large, up to 10^5 elements. This rules out any solution that would repeatedly convert prefixes to decimal using naive methods because the numbers could become extremely large and inefficient to handle. We also know that every element is either 0 or 1, which simplifies our binary calculations.

Important edge cases include arrays with only zeros, arrays of length one, and alternating sequences of ones and zeros. The problem guarantees non-empty input, so we do not need to handle an empty array.

Approaches

The brute-force approach is straightforward. For each index i, we could compute the decimal number corresponding to nums[0..i] and then check divisibility by 5. This works correctly because it directly evaluates the required property. However, it is inefficient because converting large binary prefixes to decimal repeatedly would take O(n^2) time in the worst case, and the numbers themselves could be extremely large.

The key insight for a more optimal approach is to realize that we do not need to store the entire decimal number to check divisibility by 5. Modular arithmetic allows us to keep track of the remainder of the binary number modulo 5 as we process each bit. If current is the decimal value of the prefix modulo 5, then adding a new bit b at the end is equivalent to computing (current * 2 + b) % 5. This ensures that current never grows too large, giving an O(n) time and O(1) extra space solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Converts each prefix to decimal and checks divisibility
Optimal	O(n)	O(n)	Uses modulo 5 arithmetic to maintain the remainder efficiently

Algorithm Walkthrough

1. Initialize an empty list result to store boolean values.
2. Initialize a variable current to 0, representing the decimal value of the current prefix modulo 5.
3. Iterate over each bit b in nums.
4. Update current using the formula current = (current * 2 + b) % 5. This effectively shifts the current value left by one bit and adds the new bit, keeping the result modulo 5.
5. Append True to result if current is 0 (meaning divisible by 5) and False otherwise.
6. Return the result array.

Why it works: At each step, current correctly represents the decimal value of the prefix modulo 5. Because modular arithmetic preserves divisibility properties, current == 0 if and only if the prefix number is divisible by 5. This invariant guarantees correctness without ever storing or computing large decimal numbers.

Python Solution

from typing import List

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

In this implementation, we initialize result to store the answers and current to track the prefix value modulo 5. For each bit, we update current using modular arithmetic and append a boolean indicating divisibility by 5. The code directly follows the algorithm steps and avoids large number operations.

Go Solution

func prefixesDivBy5(nums []int) []bool {
    result := make([]bool, 0, len(nums))
    current := 0
    
    for _, b := range nums {
        current = (current*2 + b) % 5
        result = append(result, current == 0)
    }
    
    return result
}

In Go, we preallocate the result slice with a capacity equal to len(nums) to improve performance. The variable current tracks the modulo 5 value as in Python. We iterate over each element, update the modulo, and append a boolean. Go handles integer operations safely in this range, and we avoid any overflow issues due to the modulo operation.

Worked Examples

Example 1: nums = [0,1,1]

i	nums[i]	current = (current*2+nums[i])%5	divisible?	result
0	0	(0*2+0)%5 = 0	True	True
1	1	(0*2+1)%5 = 1	False	False
2	1	(1*2+1)%5 = 3	False	False

Output: [True, False, False]

Example 2: nums = [1,1,1]

i	nums[i]	current	divisible?	result
0	1	1	False	False
1	1	3	False	False
2	1	2	False	False

Output: [False, False, False]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once with O(1) work per element.
Space	O(n)	We store a boolean result for each prefix. current uses O(1) space.

The algorithm is linear in both time and space. Modular arithmetic ensures we never store large decimal numbers, so performance remains efficient even for the maximum constraint of 100,000 elements.

Test Cases

# Provided examples
assert Solution().prefixesDivBy5([0,1,1]) == [True, False, False]  # Example 1
assert Solution().prefixesDivBy5([1,1,1]) == [False, False, False]  # Example 2

# Edge cases
assert Solution().prefixesDivBy5([0]) == [True]  # Single zero
assert Solution().prefixesDivBy5([1]) == [False]  # Single one
assert Solution().prefixesDivBy5([1,0,1,0,1]) == [False, False, True, False, False]  # Alternating pattern
assert Solution().prefixesDivBy5([0]*5) == [True, True, True, True, True]  # All zeros
assert Solution().prefixesDivBy5([1]*5) == [False, False, False, False, False]  # All ones

Test	Why
[0,1,1]	Validates basic binary to decimal conversion and divisibility
[1,1,1]	No prefixes divisible by 5
[0]	Edge case of smallest input with zero
[1]	Edge case of smallest input with one
[1,0,1,0,1]	Tests alternating 1s and 0s pattern
[0]*5	All zeros, should all be divisible by 5
[1]*5	All ones, no divisibility by 5

Edge Cases

One important edge case is when the array contains only zeros. The decimal value of any prefix will always be zero, which is divisible by 5. The implementation correctly identifies all zeros as True because (0*2 + 0) % 5 == 0.

A second edge case is when the array contains only ones. In this case, the binary numbers grow rapidly, but the modulo operation ensures we never compute the large decimal value directly. The algorithm correctly tracks divisibility by 5 without overflow, producing the correct boolean sequence.

A third edge case is alternating patterns of ones and zeros. Such sequences can produce decimal values that fluctuate modulo 5 unpredictably. The algorithm’s step-by-step modulo calculation handles this correctly, maintaining the invariant that current always represents the prefix value modulo 5. This prevents errors that could occur if one attempted to convert the full binary string to decimal repeatedly.