Binary Gap - Practice Coding Problems

Binary Gap - Problem

Bit Manipulation Easy

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.

Input & Output

Example 1 — Basic Gap

$ Input: n = 22

› Output: 2

💡 Note: 22 in binary is 10110. The gaps between consecutive 1's are: between positions 1 and 4 (gap = 2). Maximum gap is 2.

Example 2 — No Gap

$ Input: n = 6

› Output: 1

💡 Note: 6 in binary is 110. The gap between consecutive 1's at positions 1 and 2 is 0. But we also have trailing zeros, so gap is 1.

Example 3 — Power of 2

$ Input: n = 8

› Output: 0

💡 Note: 8 in binary is 1000. There's only one 1, so no adjacent 1's exist. Return 0.

Constraints

1 ≤ n ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Integer n = 22

Convert

Binary representation: 10110

Find Gaps

Measure distances between consecutive 1's

Key Takeaway

🎯 Key Insight: Track positions of consecutive 1 bits and calculate the maximum distance between them

Asked in

G Google 12 M Microsoft 8 A Apple 5

The key insight is to find consecutive 1's in the binary representation and measure gaps between them. Best approach uses bit manipulation to process bits directly without string conversion. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Convert to String and Find Gaps	O(log n)	O(log n)	Convert number to binary string and find all gaps between 1's
Bit Manipulation with Single Pass	O(log n)	O(1)	Use bit operations to find gaps without string conversion

Convert to String and Find Gaps — Algorithm Steps

Convert number to binary string
Find all positions where character is '1'
Calculate distances between consecutive 1 positions
Return the maximum distance found

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to Binary

Transform number to binary string representation

Find Positions

Locate all positions where bit is '1'

Calculate Gaps

Measure distances between consecutive 1's

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int n) {
    char binary[33];
    int index = 0;
    int temp = n;
    
    // Convert to binary string
    while (temp > 0) {
        binary[index++] = '0' + (temp % 2);
        temp /= 2;
    }
    binary[index] = '\0';
    
    // Reverse the string
    for (int i = 0; i < index / 2; i++) {
        char t = binary[i];
        binary[i] = binary[index - 1 - i];
        binary[index - 1 - i] = t;
    }
    
    int positions[32];
    int posCount = 0;
    
    // Find all positions of '1'
    for (int i = 0; i < index; i++) {
        if (binary[i] == '1') {
            positions[posCount++] = i;
        }
    }
    
    // If less than 2 ones, no gap exists
    if (posCount < 2) {
        return 0;
    }
    
    // Find maximum gap between consecutive 1's
    int maxGap = 0;
    for (int i = 1; i < posCount; i++) {
        int gap = positions[i] - positions[i-1] - 1;
        if (gap > maxGap) {
            maxGap = gap;
        }
    }
    
    return maxGap;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int result = solution(n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Converting to binary string takes O(log n) time, then scanning the string takes O(log n)

⚡ Linearithmic

Space Complexity

O(log n)

Storing the binary string requires O(log n) space, plus array to store positions

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Convert to String and Find Gaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler