1. Introduction

The binary gap of a number is defined as the maximum number of consecutive zeros that occur between two ones in the binary representation of the number. This problem can be solved iteratively, but in this article, we’ll present a recursive solution.

2. Solution

2.1. Algorithm

Let’s think about the problem. First, we need to find a way to extract the bits of the number, bit by bit. Next, we can notice that only when we find the first bit that is equal to one can we then start counting the number of consecutive zeros. The way of doing this is by simply passing along three variables:

  • Number: the number we are solving this problem for
  • FoundFirstOne: a boolean variable that is set to true once we find the first active bit
  • NumOfZeros: the number of consecutive zeros so far

To extract the least significant bit from a number, we can take its remainder after dividing it by 2. Similarly, to remove the least significant bit from the number, we should divide it by 2. As a result, every time we extract a bit from the number, there are two options:

  • If the extracted bit equals one, we should call the algorithm recursively after dividing the number by 2. Also, we should set FoundFirstOne to true (in case it wasn’t set yet). Finally, we should set NumOfZeros to zero because currently, we don’t have any consecutive zeros. Also, we should start counting again in case the next bit equals zero.
  • If the extracted bit equals zero, we should also call the algorithm recursively after dividing the number by 2. However, in this case, we will not change the value of FoundFirstOne. Also, we should increase NumOfZeros by one only if FoundFirstOne equals true.

In each step, we’ll return the maximum between NumOfZeros and the value returned from the recursive call. However, if this number equals zero, then the algorithm should immediately return zero, indicating that the last bit was one and this call didn’t find any consecutive zeros.

2.2. Pseudocode

The idea behind the algorithm we just described is that we can only start counting consecutive zeros after we find the first one-bit. Once the first one-bit is found, we will either increase the number of consecutive zeros by one or set it to zero in case the current bit equals one. Once the recursive call is finished, the answer will be either the value found recursively or the number of consecutive zeros we have so far.

Let’s see the psueodocode for our recursive algorithm:

Rendered by QuickLaTeX.com

The initial call of this algorithm should pass the number, set FoundFirstOne to false, and set the value of NumOfZeros to zero.

2.3. Complexity

The complexity of our recursive algorithm is O(Log2N) because the algorithm only makes one recursive call, which divides the number by 2. This means that the algorithm will make a total of Log2N steps.

3. Conclusion

In this article, we described a recursive algorithm for solving the binary gap problem.

First, we described how the algorithm works. Then, we presented the pseudocode for our algorithm, and finally, we presented the algorithm’s complexity.

Subscribe
Notify of
guest
3 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Andres Guevara
Andres Guevara
4 months ago

Nice, clear and concise

Omar Fendri
4 months ago

Thanks for the problem and the solution is interesting, however, I would argue that the correct complexity of the solution is O(N). (N is the number of digits) The algorithm is iterating all the digits. The “dividing by 2” part does not present a divide and conquer pattern. The input of the problem is a sequence of 1 and 0 and the length of the sequence is N. You have to check them all (using recursion or iteratively) to calculate the gap so there is no way that the complexity would be less than O(N). Please correct me if I’m… Read more »

Loredana Crusoveanu
Loredana Crusoveanu
4 months ago
Reply to  Omar Fendri

Hi Omar,
Glad you found the article interesting.
I’m not clear where the algorithm is iterating all the digits. Each call divides the number by 2 to extract or remove the least significant bit from the decimal number.
The recursion would hence represent a logarithmic complexity.