Binary Prefix Divisible By 5

Easy

#0972Time: 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)`.

Patterns

Bit Manipulation

Data structures

Array

Prompt

You are given a binary array nums (0-indexed).

We define x_i 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 x₀ = 1, x₁ = 2, and x₂ = 5.

Return an array of booleans answer where answer[i] is true if x_i 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 <= 10⁵
nums[i] is either 0 or 1.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Create an empty List<Boolean> called answer.
Initialize an integer remainder to 0.
Loop through each bit in the nums array.
Update the remainder using the formula: remainder = (remainder * 2 + bit) % 5.
Check if the new remainder is 0.
Add true to answer if remainder is 0, otherwise add false.
After the loop, return answer.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<Boolean> prefixesDivBy5(int[] nums) {6        List<Boolean> answer = new ArrayList<>();7        int remainder = 0;8        for (int bit : nums) {9            // Update remainder: remainder = (remainder * 2 + bit) % 510            // This can be written as a left shift for multiplication by 211            remainder = ((remainder << 1) | bit) % 5;12            answer.add(remainder == 0);13        }14        return answer;15    }16}

Complexity

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

Trade-offs

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.

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.

Algorithm

Initialize an empty list of booleans, answer.
Initialize a BigInteger variable, currentNum, to zero.
Iterate through the input array nums from left to right.
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].
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.
Append true to the answer list if it's divisible, and false otherwise.
After iterating through all the numbers in nums, return the answer list.

Walkthrough

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.

1import java.math.BigInteger;2import java.util.ArrayList;3import java.util.List;4 5class Solution {6    public List<Boolean> prefixesDivBy5(int[] nums) {7        List<Boolean> answer = new ArrayList<>();8        BigInteger currentNum = BigInteger.ZERO;9        BigInteger five = BigInteger.valueOf(5);10        BigInteger two = BigInteger.valueOf(2);11 12        for (int bit : nums) {13            // currentNum = currentNum * 2 + bit14            currentNum = currentNum.multiply(two).add(BigInteger.valueOf(bit));15            // Check if currentNum % 5 == 016            if (currentNum.mod(five).equals(BigInteger.ZERO)) {17                answer.add(true);18            } else {19                answer.add(false);20            }21        }22        return answer;23    }24}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  List<Boolean> prefixesDivBy5(int[] nums) {4    List<Boolean> ans = new ArrayList<>();5    int x = 0;6    for (int v : nums) {7      x = (x << 1 | v) % 5;8      ans.add(x == 0);9    }10    return ans;11  }12}

1class Solution {2public:3  vector<bool> prefixesDivBy5(vector<int> &nums) {4    vector<bool> ans;5    int x = 0;6    for (int v : nums) {7      x = (x << 1 | v) % 5;8      ans.push_back(x == 0);9    }10    return ans;11  }12};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem