algoadvance

You need to implement a function prefixesDivBy5 that takes a list of binary digits A (i.e., a list of values that are either 0 or 1) and returns a list of boolean values. Each boolean value at index i indicates whether the binary number represented by the first i+1 elements of A is divisible by 5.

For example, given a list A = [0, 1, 1], the output should be [True, False, False] because:

• The binary number represented by the first element 0 is 0 which is divisible by 5.
• The binary number represented by the first two elements 01 is 1 which is not divisible by 5.
• The binary number represented by the first three elements 011 is 3 which is not divisible by 5.

Clarifying Questions

1. Q: What is the length range of the input list A? A: The input list A will have a length between 1 and 30000.

2. Q: Are the elements of the list A guaranteed to be binary digits (0 or 1)? A: Yes, all elements in the list A are guaranteed to be either 0 or 1.

3. Q: What should be returned in the case of an empty list? A: The problem guarantees that the list will have a length of at least 1, so this case does not need to be handled.

Strategy

To solve this problem, we can follow these steps:

1. Iterate through the list while constructing the binary number represented by the prefix.
2. Use modular arithmetic to check if the current prefix is divisible by 5.
3. Collect the results in a list and return it.

To avoid handling very large binary numbers directly, we can use the property (a * 2 + b) % c == (a % c * 2 + b % c) % c to keep the current number modulo 5. This allows us to manage the size of our intermediate calculations efficiently.

Steps:

1. Initialize a variable current_number to 0.
2. Initialize the result list result to an empty list.
3. Iterate through each element of A:
   • Update current_number using current_number = (current_number * 2 + digit) % 5.
   • Append True to result if current_number is 0, otherwise append False.
4. Return the result list.

Code

from typing import List

def prefixesDivBy5(A: List[int]) -> List[bool]:
    result = []
    current_number = 0
    for digit in A:
        current_number = (current_number * 2 + digit) % 5
        result.append(current_number == 0)
    return result

# Example usage
A = [0, 1, 1]
print(prefixesDivBy5(A))  # Output: [True, False, False]

Time Complexity

• Time Complexity: O(n), where n is the length of the input list A. We only traverse the list once and perform constant time operations for each element.
• Space Complexity: O(n), for storing the boolean results in the list.

Try our interview co-pilot at AlgoAdvance.com

• 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?