We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Gap

Number: 899

Difficulty: Easy

Paid? No

Companies: X, eBay

Problem Description

Given a positive integer n, find and return the longest distance between any two adjacent 1's in its binary representation. Two 1's are considered adjacent if there are only 0's (or none) between them. If there are no two adjacent 1's, return 0.

Key Insights

  • Convert the integer to its binary representation without needing to store the entire string.
  • Iterate over the bits, tracking the positions where you encounter a 1.
  • Compute the gap between consecutive 1's and update the maximum gap.
  • Utilize bitwise operations to efficiently process each bit.

Space and Time Complexity

Time Complexity: O(N) where N is the number of bits in n (typically constant, e.g., 32 bits for n <= 10^9).
Space Complexity: O(1) additional space.

Solution

We solve the problem by processing the number bit by bit using bitwise operations. As we iterate through the bits, we maintain a variable to record the position of the last seen 1. For each 1 found, if it is not the first one, we compute the distance (difference in bit positions) from the last 1 and update our maximum gap accordingly. This approach avoids converting the entire number into a string and uses constant space.

Code Solutions

# Python solution for Binary Gap problem

def binaryGap(n):
    # Initialize variables to store the last seen index of '1' and maximum gap
    last_one_position = -1  # Stores the index of the last observed '1'
    max_gap = 0             # Maximum gap between consecutive '1's
    position = 0            # Current bit position (starting from 0)
    
    # Iterate until n becomes 0
    while n:
        # Check if the current bit is '1'
        if n & 1:
            # If this is not the first '1', update max_gap
            if last_one_position != -1:
                max_gap = max(max_gap, position - last_one_position)
            # Update the last seen position with the current index
            last_one_position = position
        # Shift n to the right by one bit and increment the bit position
        n = n >> 1
        position += 1
    return max_gap

# Example usage
print(binaryGap(22))  # Expected output: 2
← Back to All Questions