We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Prefix Divisible By 5

Difficulty: Easy

Problem 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). Return an array of booleans answer where answer[i] is true if x_i is divisible by 5.

Key Insights

  • Each prefix of the binary array represents a number that can be derived from the binary representation.
  • A number is divisible by 5 if the remainder when divided by 5 is zero.
  • Instead of converting the entire binary prefix to a decimal number, we can keep track of the value using modular arithmetic to avoid large number computations.
  • The binary representation allows us to build the number by shifting and adding, which can be efficiently handled using the properties of modulo.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can iterate through the binary array while maintaining the current value of the binary prefix modulo 5. For each element in the array, we can update this value by shifting the previous value to the left (which is equivalent to multiplying by 2) and adding the current element. We then check if the updated value is divisible by 5 and store the result in a boolean array.

Data Structures:

  • An array to store boolean results.

Algorithmic Approach:

  1. Initialize a variable to keep track of the current binary value modulo 5.
  2. Iterate through the binary array:
    • Update the current value by shifting left and adding the current bit.
    • Check if the value is divisible by 5 and append the result to the answer array.
  3. Return the answer array.

Code Solutions

def prefixesDivBy5(nums):
    answer = []
    current = 0
    for num in nums:
        current = (current << 1 | num) % 5  # Shift left and add the current num, then take modulo 5
        answer.append(current == 0)  # Check if current value is divisible by 5
    return answer
← Back to All Questions