Binary Gap

Easy

Asked by:

7 views

Topics:

Bit Manipulation

Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.

Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.

Example 1:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:

Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 3:

Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Constraints:

1 <= n <= 10⁹

Binary Gap

Easy

Asked by:

7 views

Topics:

Bit Manipulation

Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.

Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.

Example 1:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:

Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 3:

Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Constraints:

1 <= n <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the integer N? Can it be zero or negative?
What should I return if the binary representation of N contains only zeros or only ones, i.e., no binary gap?
By 'binary gap', do you mean the maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N?
Could you clarify what output I should return if there are multiple binary gaps of the same maximal length? Should I return any one of them or is there a specific one you want me to prioritize?
Are you looking for the length of the *longest* binary gap, or just *a* binary gap?

Brute Force Solution

Approach

The brute force strategy is like painstakingly examining every possibility. We will convert the number to its binary representation and then explore every possible gap between ones to find the biggest one.

Here's how the algorithm would work step-by-step:

First, turn the number into its binary form. Think of it as a sequence of zeros and ones.
Go through the sequence from start to finish, looking for a 'one'.
Once you find a 'one', start counting the number of consecutive 'zeros' that follow it.
When you encounter another 'one', stop counting the zeros. This counts the number of zeros between two ones.
Remember this count. Then, continue scanning the remaining part of the binary sequence, looking for the next 'one'.
Repeat steps 3-5 until you have examined the entire sequence.
Finally, compare all the counts you remembered, and find the largest one. This is the largest gap.

Code Implementation

def binary_gap_brute_force(number):
    binary_representation = bin(number)[2:]
    maximum_gap = 0
    current_gap = 0
    found_first_one = False

    for bit in binary_representation:
        if bit == '1':
            # If this is the second '1' found, compare gaps
            if found_first_one:
                maximum_gap = max(maximum_gap, current_gap)
                current_gap = 0
            else:
                found_first_one = True

        elif found_first_one:
            # Only count zeros after the first '1'
            current_gap += 1

    return maximum_gap

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm first converts the input integer to its binary representation. The number of bits in the binary representation is logarithmic with respect to the input number n (specifically, log base 2 of n). The algorithm then iterates through this binary representation once to find the largest gap between ones. Therefore, the time complexity is determined by the number of bits, which is O(log n).

Space Complexity

O(1) – The provided algorithm converts the input number into its binary representation, which in most implementations happens in place or using a fixed-size buffer. The algorithm then iterates through this binary representation, keeping track of the current gap size and the maximum gap size seen so far. These variables for storing gap sizes require constant extra space. Thus, the space complexity is independent of the size of the input number and is constant.

Optimal Solution

Approach

The best way to find the biggest gap between ones in a binary number is to keep track of the positions of the ones. We'll scan the binary representation from left to right, remembering the last seen one, and calculating the gap each time we find a new one.

Here's how the algorithm would work step-by-step:

Convert the given number into its binary form. Don't worry about storing the entire binary form; we can process it on the fly.
Start reading the binary representation from left to right.
The first time you see a 'one', remember its position. This is the 'previous one'.
As you keep reading, every time you find another 'one', calculate the distance (gap) between its position and the position of the 'previous one'.
Keep track of the largest gap you've found so far.
Update the 'previous one' to be the position of this new 'one'.
Repeat this process until you've reached the end of the binary representation.
The largest gap you tracked is the answer.

Code Implementation

def binary_gap(number):
    last_one_position = None
    maximum_gap = 0

    # Iterate through bits
    for index in range(number.bit_length()):
        # Check if the current bit is a 1
        if (number >> index) & 1:
            # First 1 found
            if last_one_position is None:
                last_one_position = index

            else:
                # Gap between current and last 1
                current_gap = index - last_one_position

                # Store the largest gap found so far
                maximum_gap = max(maximum_gap, current_gap)

                last_one_position = index

    return maximum_gap

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The input to this problem is the integer n. The dominant operation is converting the integer into its binary representation and iterating through it. The number of bits in the binary representation of n is log base 2 of n (or simply log n). We iterate through each bit to find the gaps. Therefore, the time complexity is proportional to the number of bits, which is O(log n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables: one to store the 'previous one' position and another to track the 'largest gap'. The number of bits in the input number N, which determines the length of the binary representation, doesn't affect the amount of extra memory used. Therefore, the auxiliary space remains constant, regardless of the input number N. This constant space usage is represented as O(1).

Edge Cases

Case	How to Handle
N is 0	Return 0 as the binary representation has no gaps.
N is 1	Return 0 as the binary representation has no gaps.
N is a power of 2 (e.g., 2, 4, 8, 16)	Return 0 because there are no two '1's with a '0' in between.
N has leading zeros in its binary representation	The algorithm will ignore leading zeros when searching for '1' bits.
N has no gaps (e.g., 3, 7, 15)	Return 0 as there are no gaps between 1s.
N is the maximum integer value (2147483647)	The algorithm should correctly handle the large number without integer overflow issues because it uses bitwise operations.
N has a single gap	The algorithm correctly computes the length of this single gap.
N has multiple gaps of varying lengths	The algorithm correctly identifies and returns the maximum gap length.