Leetcode – Binary Prefix Divisible By 5 Solution

Spread the love

Binary numbers form the core foundation of computer science. As we’ve transitioned into a digital age, binary operations and their manipulations have become increasingly prevalent in coding challenges. One such interesting problem on Leetcode is the “Binary Prefix Divisible By 5”. This problem not only tests one’s understanding of binary numbers but also incorporates mathematical concepts. In this article, we’ll dissect this problem and present a step-by-step Python solution.

Table of Contents

  1. Problem Statement
  2. Understanding Binary Numbers
  3. The Mathematics Behind the Problem
  4. Solution Strategy
  5. Python Implementation
  6. Time and Space Complexity Analysis
  7. Conclusion

1. Problem Statement

Given an array A consisting of N integers (either 0 or 1), interpret it as the binary representation of a number. For every prefix of the array, check if the number formed by that prefix is divisible by 5.

Return an array answer where answer[i] is True if the first (i+1) elements of A are divisible by 5.

Example:

Input: A = [1,0,1]
Output: [False, False, True]
Explanation: 
The numbers formed by the prefixes are:
1 -> Not divisible by 5
10 -> Not divisible by 5
101 -> Divisible by 5

2. Understanding Binary Numbers

Binary is a base-2 system, meaning it only has two digits: 0 and 1. When we read a binary number from left to right, each position represents an increasing power of 2.

For instance, the binary number 101 in base 10 (decimal) is calculated as:

3. The Mathematics Behind the Problem

To efficiently check if each prefix of the array is divisible by 5, we don’t need to compute the whole number for each prefix. Instead, we can keep track of the current number and update it as we traverse the array.

Given a number x, if you append a bit b to its end in binary, the new number becomes 2x + b.

4. Solution Strategy

  1. Initialize current_num to 0.
  2. Traverse through the array. For each bit:
    • Update the current_num: current_num=2×current_num+bit
    • Check if current_num is divisible by 5. Append the result to the answer list.
    • Use modulo operation to avoid overflow: current_num=current_num%5

5. Python Implementation

def prefixesDivBy5(A):
    answer = []
    current_num = 0
    
    for bit in A:
        # Update current number and take modulo to avoid overflow
        current_num = (2 * current_num + bit) % 5
        answer.append(current_num == 0)
    
    return answer

6. Time and Space Complexity Analysis

  • Time Complexity:
    • We’re traversing the array once and performing constant-time operations for each element.
    • Thus, the time complexity is O(n), where n is the length of the array.
  • Space Complexity:
    • We are using an extra array (answer) that has the same length as the input array.
    • Thus, the space complexity is O(n).

7. Conclusion

The “Binary Prefix Divisible By 5” problem on Leetcode elegantly fuses the realms of binary operations and mathematical insights. It serves as a brilliant example of how computer science problems often require a combination of domain knowledge and algorithmic thinking.

Leave a Reply