868. Binary Gap - Solution & Explanation

The problem

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⁹

Approach overview

Problem Overview: You are given a positive integer n. Convert it to binary and return the longest distance between two consecutive 1 bits. The distance is measured by the difference in their positions. If there are fewer than two 1 bits, the result is 0.

The key observation: the binary representation determines the gaps. Once you know where each 1 appears, the problem reduces to tracking the maximum difference between consecutive positions. This is a classic bit manipulation exercise and appears frequently in entry-level coding interviews.

Approach 1: Convert to Binary and Find Gaps (O(log n) time, O(1) space)

Iterate through the bits of the number directly using bit operations. Repeatedly check the least significant bit using n & 1, then right shift with n >>= 1. Maintain the index of the last seen 1. Every time another 1 appears, compute the gap between the current index and the previous index, and update the maximum gap.

This method avoids creating a string or additional data structures. The loop runs once per bit of the number, which is proportional to log2(n). Space stays constant because only a few integer variables are tracked. This approach demonstrates practical use of bitwise operators and is the most natural solution when practicing bit manipulation problems.

Approach 2: String Conversion Method (O(log n) time, O(log n) space)

Convert the integer to its binary representation using built‑in utilities such as bin(n) in Python or Integer.toBinaryString(n) in Java. After conversion, iterate through the resulting string and record the positions of each '1'. For every new '1', compute the difference from the previous index and update the maximum gap.

This version trades a bit of memory for readability. The logic becomes straightforward because you operate on characters rather than individual bits. The time complexity is still O(log n) since the binary string length is proportional to the number of bits. Space complexity becomes O(log n) due to storing the binary string. This approach also touches concepts related to string processing.

Recommended for interviews: The bit‑iteration approach is usually preferred. Interviewers expect you to recognize that binary gaps depend only on bit positions and can be solved with simple shifts and bit checks. The string method is acceptable and easy to implement, but the bit manipulation version demonstrates stronger understanding of binary representation and space optimization.

Approach 1: Approach 1: Convert to Binary and Find Gaps

This approach involves converting the number into its binary representation and then finding the positions of '1's. We will iterate through the binary string, keep track of the last position where a '1' was found, and calculate the distance from the current '1' to the last. Record the maximum distance found.

Python

def binary_gap(n):
    last_position = -1
    max_gap = 0
    idx = 0
    while n > 0:
        if n & 1:
            if last_position != -1:
                max_gap = max(max_gap, idx - last_position)
            last_position = idx
        n >>= 1
        idx += 1
    return max_gap

print(binary_gap(22))  # Output: 2

Java

public class BinaryGap {
    public static int binaryGap(int n) {
        int lastPosition = -1, maxGap = 0, idx = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                if (lastPosition != -1) {
                    maxGap = Math.max(maxGap, idx - lastPosition);
                }
                lastPosition = idx;
            }
            n >>= 1;
            idx++;
        }
        return maxGap;
    }
    public static void main(String[] args) {
        System.out.println(binaryGap(22));  // Output: 2
    }
}

C++

#include <iostream>
#include <algorithm>
using namespace std;

int binaryGap(int n) {
    int lastPosition = -1, maxGap = 0, idx = 0;
    while (n > 0) {
        if (n & 1) {
            if (lastPosition != -1) {
                maxGap = max(maxGap, idx - lastPosition);
            }
            lastPosition = idx;
        }
        n >>= 1;
        idx++;
    }
    return maxGap;
}

int main() {
    cout << binaryGap(22) << endl; // Output: 2
    return 0;
}

JavaScript

function binaryGap(n) {
    let lastPosition = -1, maxGap = 0, idx = 0;
    while (n > 0) {
        if (n & 1) {
            if (lastPosition !== -1) {
                maxGap = Math.max(maxGap, idx - lastPosition);
            }
            lastPosition = idx;
        }
        n >>= 1;
        idx++;
    }
    return maxGap;
}

console.log(binaryGap(22));  // Output: 2

#include <stdio.h>
#include <math.h>

int binaryGap(int n) {
    int lastPosition = -1, maxGap = 0, idx = 0;
    while (n > 0) {
        if (n & 1) { // If the current bit is 1
            if (lastPosition != -1) {
                maxGap = fmax(maxGap, idx - lastPosition);
            }
            lastPosition = idx;
        }
        n >>= 1;
        idx++;
    }
    return maxGap;
}

int main() {
    printf("%d\n", binaryGap(22)); // Output: 2
    return 0;
}

using System;

public class Program {
    public static int BinaryGap(int n) {
        int lastPosition = -1, maxGap = 0, idx = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                if (lastPosition != -1) {
                    maxGap = Math.Max(maxGap, idx - lastPosition);
                }
                lastPosition = idx;
            }
            n >>= 1;
            idx++;
        }
        return maxGap;
    }
    public static void Main() {
        Console.WriteLine(BinaryGap(22));  // Output: 2
    }
}

We handle the number bit by bit, checking for '1's and calculating the maximum gap with simple bitwise operations.

Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Approach 2: String Conversion Method

This approach involves converting the integer to its binary string representation, iterating through the string to find indices of '1's, and calculating and storing the distances between consecutive '1's to find the maximum gap.

Python

def binary_gap(n):
    bin_str = bin(n)[2:]  # Convert to binary and remove '0b'
    last_position = -1
    max_gap = 0
    for i in range(len(bin_str)):
        if bin_str[i] == '1':
            if last_position != -1:
                max_gap = max(max_gap, i - last_position)
            last_position = i
    return max_gap

print(binary_gap(22))  # Output: 2

Java

public class BinaryGap {
    public static int binaryGap(int n) {
        String binStr = Integer.toBinaryString(n);
        int lastPosition = -1, maxGap = 0;
        for (int i = 0; i < binStr.length(); i++) {
            if (binStr.charAt(i) == '1') {
                if (lastPosition != -1) {
                    maxGap = Math.max(maxGap, i - lastPosition);
                }
                lastPosition = i;
            }
        }
        return maxGap;
    }
    public static void main(String[] args) {
        System.out.println(binaryGap(22));  // Output: 2
    }
}

C++

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int binaryGap(int n) {
    string binStr = "";
    while (n > 0) {
        binStr = (char)((n % 2) + '0') + binStr;
        n /= 2;
    }
    int lastPosition = -1, maxGap = 0;
    for (int i = 0; i < binStr.length(); ++i) {
        if (binStr[i] == '1') {
            if (lastPosition != -1) {
                maxGap = max(maxGap, i - lastPosition);
            }
            lastPosition = i;
        }
    }
    return maxGap;
}

int main() {
    cout << binaryGap(22) << endl; // Output: 2
    return 0;
}

JavaScript

function binaryGap(n) {
    const binStr = n.toString(2);
    let lastPosition = -1, maxGap = 0;
    for (let i = 0; i < binStr.length; i++) {
        if (binStr[i] === '1') {
            if (lastPosition !== -1) {
                maxGap = Math.max(maxGap, i - lastPosition);
            }
            lastPosition = i;
        }
    }
    return maxGap;
}

console.log(binaryGap(22));  // Output: 2

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

int binaryGap(int n) {
    char binStr[32];
    int idx = 0, length = 0, lastPosition = -1, maxGap = 0;
    while (n > 0) {
        binStr[length++] = (n % 2) ? '1' : '0';
        n /= 2;
    }
    for (int i = 0; i < length; ++i) {
        if (binStr[i] == '1') {
            if (lastPosition != -1) {
                int gap = i - lastPosition;
                if (gap > maxGap) maxGap = gap;
            }
            lastPosition = i;
        }
    }
    return maxGap;
}

int main() {
    printf("%d\n", binaryGap(22));  // Output: 2
    return 0;
}

using System;

public class Program {
    public static int BinaryGap(int n) {
        string binStr = Convert.ToString(n, 2);
        int lastPosition = -1, maxGap = 0;
        for (int i = 0; i < binStr.Length; i++) {
            if (binStr[i] == '1') {
                if (lastPosition != -1) {
                    maxGap = Math.Max(maxGap, i - lastPosition);
                }
                lastPosition = i;
            }
        }
        return maxGap;
    }
    public static void Main() {
        Console.WriteLine(BinaryGap(22));  // Output: 2
    }
}

Convert to a binary string using Python's `bin` function, strip leading '0b', then iterate over the positions of '1's.

Complexity

Time Complexity: O(log n)
Space Complexity: O(log n)

Try this approach in the editor

Approach 3: Bit Manipulation

We use two pointers pre and cur to represent the positions of the previous and current 1 bits, respectively. Initially, pre = 100 and cur = 0. Then, we traverse the binary representation of n. When we encounter a 1, we calculate the distance between the current position and the previous 1 position and update the answer.

The time complexity is O(log n), where n is the given integer. The space complexity is O(1).

TypeScript

function binaryGap(n: number): number {
    let ans = 0;
    for (let pre = 100, cur = 0; n; n >>= 1) {
        if (n & 1) {
            ans = Math.max(ans, cur - pre);
            pre = cur;
        }
        ++cur;
    }
    return ans;
}

func binaryGap(n int) (ans int) {
	for pre, cur := 100, 0; n != 0; n >>= 1 {
		if n&1 == 1 {
			ans = max(ans, cur-pre)
			pre = cur
		}
		cur++
	}
	return
}

Rust

impl Solution {
    pub fn binary_gap(mut n: i32) -> i32 {
        let mut ans = 0;
        let mut pre = 100;
        let mut cur = 0;
        while n != 0 {
            if n % 2 == 1 {
                ans = ans.max(cur - pre);
                pre = cur;
            }
            cur += 1;
            n >>= 1;
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Convert to Binary and Find Gaps	Time Complexity: O(log n) Space Complexity: O(1)
Approach 2: String Conversion Method	Time Complexity: O(log n) Space Complexity: O(log n)
Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Convert to Binary and Scan Bits	O(log n)	O(1)	Best for interviews and optimal memory usage using bitwise operations
String Conversion Method	O(log n)	O(log n)	Simpler implementation when readability is preferred over strict space optimization

Frequently asked questions

Is Binary Gap easy or hard?

Binary Gap is classified as an Easy problem. The challenge mainly involves understanding binary representation and tracking the distance between consecutive 1 bits. It is commonly used to introduce bit manipulation concepts.

Binary Gap Python/Java solution

In Python, convert using bin(n) or iterate with bit operations while shifting the number. In Java, use Integer.toBinaryString(n) for the string approach or bitwise operations like (n & 1) and n >>= 1. Both implementations run in O(log n) time.

How to solve Binary Gap in O(log n)?

Process the binary representation one bit at a time. Maintain the position of the previous 1 bit, and whenever another 1 appears, compute the distance between indices. Update the maximum gap and continue shifting the number right until all bits are processed.

What is the best approach for Binary Gap?

The most efficient approach iterates through the bits of the number using bit manipulation. Check each bit with n & 1 and shift the number right using n >> 1 while tracking the index of the last seen 1. This runs in O(log n) time and O(1) space because the loop processes each bit once without creating extra data structures.

Is Binary Gap asked at Google/Amazon/Meta?

Binary Gap is typically categorized as an easy bit manipulation problem and appears in screening rounds or practice sets rather than deep system interviews. Similar bit scanning and binary representation problems do appear at companies like Amazon and Google for early-stage coding rounds.

What data structure is used in Binary Gap?

No complex data structure is required. The optimal approach relies on bit manipulation with simple integer variables to track bit positions. An alternative implementation may use a string representation of the binary number.

What is the time complexity of Binary Gap?

The time complexity is O(log n) because the algorithm processes one bit per iteration and an integer has log2(n) bits. Both the bit manipulation approach and the binary string approach have the same time complexity, though the string version uses additional memory.

Binary Gap solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Convert to Binary and Find Gaps

Approach 2: Approach 2: String Conversion Method

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Binary Gap solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Convert to Binary and Find Gaps

Approach 2: Approach 2: String Conversion Method

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems