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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Prefix Divisible By 5

Number: 1071

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a binary array, for every subarray prefix (from the beginning of the array up to the current index), determine if the number represented by that binary substring is divisible by 5. Return an array of booleans where each entry corresponds to whether the prefix number is divisible by 5.

Key Insights

  • Convert the binary prefix into an integer iteratively.
  • Instead of computing large numbers, maintain the remainder modulo 5.
  • Use the recurrence: remainder = (remainder * 2 + current_bit) % 5.
  • Check divisibility by simply testing if the remainder is 0.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array. Space Complexity: O(n) for the output array.

Solution

We iterate through the input binary array and update a variable that holds the current number modulo 5 using the formula: remainder = (remainder * 2 + current_bit) % 5. Since the only thing that matters for divisibility by 5 is this remainder, we avoid constructing huge numbers. For each prefix, if the remainder is 0, add true to the answer array; otherwise, add false.

Code Solutions

# Python solution for Binary Prefix Divisible By 5

def prefixesDivBy5(nums):
    # Initialize the remainder variable and the answer list.
    remainder = 0
    result = []
    
    # Iterate over each bit in the input array.
    for bit in nums:
        # Update the remainder as the number represented by the prefix.
        remainder = (remainder * 2 + bit) % 5
        # Append True if the remainder is 0 (divisible by 5), else False.
        result.append(remainder == 0)
    
    return result

# Example usage:
# nums = [0,1,1]
# print(prefixesDivBy5(nums))  # Output: [True, False, False]
← Back to All Questions