Binary Prefix Divisible By 5

EASY

Description

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

Checkout 2 different approaches to solve Binary Prefix Divisible By 5. Click on different approaches to view the approach and algorithm in detail.

Efficient Approach using Modular Arithmetic

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.

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.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> answer = new ArrayList<>();
        int remainder = 0;
        for (int bit : nums) {
            // Update remainder: remainder = (remainder * 2 + bit) % 5
            // This can be written as a left shift for multiplication by 2
            remainder = ((remainder << 1) | bit) % 5;
            answer.add(remainder == 0);
        }
        return answer;
    }
}

Complexity Analysis

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

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Binary Prefix Divisible By 5. Click on different languages to view the code.

class Solution {
public
  List<Boolean> prefixesDivBy5(int[] nums) {
    List<Boolean> ans = new ArrayList<>();
    int x = 0;
    for (int v : nums) {
      x = (x << 1 | v) % 5;
      ans.add(x == 0);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Binary Prefix Divisible By 5

Patterns:

Bit Manipulation

Data Structures:

Array