algoadvance

Leetcode 1018. Binary Prefix Divisible By 5

Problem Statement

You are given a binary array A (an array of 0s and 1s).

A binary prefix is any array that can be obtained by removing some (possibly none) elements from the end of the array.

Return a list of booleans answer, where answer[i] is true if the binary number represented by the prefix A[0] to A[i] is divisible by 5.

Example

Input: A = [0,1,1]
Output: [true,false,false]
Explanation:

• The input array is [0, 1, 1].
• The prefix “0” is “0” in binary, which is 0 in decimal. 0 is divisible by 5.
• The prefix “01” is “1” in binary, which is 1 in decimal. 1 is not divisible by 5.
• The prefix “011” is “3” in binary, which is 3 in decimal. 3 is not divisible by 5.

Clarifying Questions

1. Can A contain only 0s and 1s?
   • Yes, A is a binary array.
2. What is the maximum size of the array A?
   • According to typical competitive programming constraints, let’s assume the size of A can be up to 10000.
3. Should the function return the results for each prefix in the same order?
   • Yes, the output list should correspond to the prefix ending at each index in the input list.

Strategy

1. To determine if a prefix is divisible by 5, we do not need to convert the whole binary prefix to a decimal number explicitly.
2. We can keep track of the current number modulo 5 (current_number % 5), and update this residue as we iterate through the array.
3. When a new bit is added to the current number, we can update the residue using the equation:
   • current_number = current_number * 2 + A[i]
   • current_number % 5 = (current_number * 2 + A[i]) % 5
4. We can directly calculate (current_number * 2 + A[i]) % 5 by using modular arithmetic properties.
5. If current_number % 5 is 0 at any step, it indicates that the number formed by the current prefix is divisible by 5.

Code

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

public class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        List<Boolean> result = new ArrayList<>();
        int currentNumber = 0;
        
        for (int bit : A) {
            currentNumber = (currentNumber * 2 + bit) % 5;
            result.add(currentNumber == 0);
        }
        
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] A = {0, 1, 1};
        System.out.println(sol.prefixesDivBy5(A)); // [true, false, false]
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of array A. Each element is processed once.
• Space Complexity: O(n), for storing the result list answer.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?