algoadvance

Leetcode 1018. Binary Prefix Divisible By 5

Problem Statement

Given an array A of binary digits (0s and 1s), you need to return a list of booleans answers, where answers[i] is true if the binary number represented by the prefix A[0] to A[i] is divisible by 5.

For example:

Clarifying Questions

  1. Input Constraints:
    • What is the length range of array A?
      • Typically, the length can vary from 1 to 30000.
    • Are there only binary digits (0 or 1) in array A?
      • Yes, array A contains only 0 or 1.
  2. Output Constraints:
    • The output should be an array of boolean values (true/false) of the same length as input array A.
  3. Performance Constraints:
    • Should the solution be optimized for both time and space complexity?
      • Yes, it is preferable.

Strategy

  1. Initialize a variable num to 0. This variable will represent the current binary number formed by the prefix.
  2. Iterate through the array A, and for each digit:
    • Left shift the num by 1 bit and add the current digit to num. This effectively builds the binary number.
    • To avoid handling very large numbers, use modulo operation num % 5 to keep num manageable.
    • Check if the num is divisible by 5, and append the result (true or false) to the answer list.

This strategy ensures that we work with manageable numbers and avoids potential overflow issues. Modulo operation aids in keeping the number within practical bounds.

Time Complexity

The time complexity of this approach is O(n), where n is the length of the input array A. Each element is processed exactly once.

Code

#include <vector>

std::vector<bool> prefixesDivBy5(std::vector<int>& A) {
    std::vector<bool> result;
    int num = 0;
    
    for (int digit : A) {
        // Left shift num by 1 and add the current digit
        num = ((num << 1) + digit) % 5;
        // Check if current num is divisible by 5
        result.push_back(num == 0);
    }
    
    return result;
}

Here’s the functionality breakdown:

This solution is both efficient and straightforward. Each binary digit is processed in constant time, ensuring an O(n) complexity overall.

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