algoadvance

Problem Statement:

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.

Clarifying Questions:

1. What is the range of the input number n?
   • It is a positive integer.
2. What do we consider as “adjacent” 1’s in the binary representation?
   • Two 1’s are considered adjacent if there are no other 1’s between them in the binary representation.

Strategy:

1. Convert the integer n into its binary representation using Python’s bin() function.
2. Iterate over the binary representation to find indices of each ‘1’.
3. Calculate the distances between consecutive indices of ‘1’s.
4. Return the maximum distance found. If there’s no two adjacent 1’s, return 0.

Code:

def binaryGap(n: int) -> int:
    # Convert the integer to binary string and strip the '0b' prefix
    binary_representation = bin(n)[2:]
    
    # Variable to store the maximum gap
    max_gap = 0
    
    # Previous index of '1' found
    prev_index = -1
    
    # Iterate through the binary representation
    for i, char in enumerate(binary_representation):
        if char == '1':
            if prev_index != -1:
                # Calculate the distance between current and previous '1'
                max_gap = max(max_gap, i - prev_index)
            # Update the previous index to current index
            prev_index = i
    
    return max_gap

Time Complexity:

• Converting the number to a binary string takes O(log n) time, where n is the input number, as the length of the binary string is proportional to the logarithm of the number.
• Iterating through the binary string takes O(log n) time as well.
• Therefore, the overall time complexity is O(log n).

This solution effectively handles the transformation of a number to its binary representation and identifies the maximum gap between consecutive ‘1’s in that representation. Let’s test it with a couple of inputs:

Example Runs:

1. Input: n = 22 (which is 10110 in binary)
   • Output: 2
2. Input: n = 5 (which is 101 in binary)
   • Output: 2
3. Input: n = 6 (which is 110 in binary)
   • Output: 1
4. Input: n = 8 (which is 1000 in binary)
   • Output: 0

With this code and explanation, you should be able to handle the problem effectively.

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?