Binary Prefix Divisible By 5 - Leetcode Solution

Problem Statement:

Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit).

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example:

Input: [0,1,1] Output: [true,false,false] Explanation: The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10. Only the first number is divisible by 5, so answer[0] is true.

Solution:

The problem can be solved using the concept of modular arithmetic. To check whether a number is divisible by 5 or not, we need to check its remainder when divided by 5. If the remainder is 0, the number is divisible by 5, otherwise not.

To check the remainder when a binary number is divided by 5, we can use the fact that:

1. When a binary number is multiplied by 2, its decimal value is doubled.
2. When a binary number is multiplied by 2 and then 1 is added, its decimal value is doubled and then 1 is added.

These two properties can be used to calculate the decimal value of any binary number.

For example, consider the binary number 101. Using the first property, its decimal value is calculated as follows:

(1 * 2^2) + (0 * 2^1) + (1 * 2^0) = 5

Using the second property, its decimal value is calculated as follows:

(1 * 2^2) + (0 * 2^1) + (1 * 2^0) + 1 = 6

Now, to check whether a binary number is divisible by 5 or not, we can keep track of the remainder when the binary number is multiplied by 2 and then either 0 or 1 is added. If the remainder is 0, the binary number is divisible by 5.

Let's see how we can use this approach to solve the problem.

Algorithm:

1. Initialize a variable "remainder" to 0.
2. Initialize an empty list "result".
3. Loop through each element "num" in the input array.
4. Multiply the current value of "remainder" by 2 and add "num" to it. Set the result to "temp".
5. If "temp" is divisible by 5, append "True" to the "result" list, otherwise, append "False".
6. Update the value of "remainder" with "temp" modulo 5.
7. Return the "result" list.

Code:

class Solution: def prefixesDivBy5(self, A: List[int]) -> List[bool]: remainder = 0 result = [] for num in A: temp = (remainder * 2 + num) result.append(temp % 5 == 0) remainder = temp % 5 return result

The time complexity of this algorithm is O(n), where n is the length of the input array, as we are iterating through the array once.

This solution runs in 40 ms and takes 14.3 MB memory in Leetcode.

1