Scale Engineer

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 xi 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 x0 = 1, x1 = 2, and x2 = 5.

Return an array of booleans answer where answer[i] is true if xi 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 <= 105
  • 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

  1. Create an empty List<Boolean> called answer.
  2. Initialize an integer remainder to 0.
  3. Loop through each bit in the nums array.
  4. Update the remainder using the formula: remainder = (remainder * 2 + bit) % 5.
  5. Check if the new remainder is 0.
  6. Add true to answer if remainder is 0, otherwise add false.
  7. 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.

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

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.

Solutions

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 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 →

Next problem