Skip to main content
Talentd

Binary Gap - Solution & Explanation

EasyBit Manipulation16 min readAsked at: Amazon, Microsoft, eBay +3
Practice this problem

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.

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 <= 109

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.

We use bitwise operations to track positions of '1's in the binary form of 'n'. Each time a '1' is encountered, compare the current index with the last position of '1' to update the maximum gap. Shift bit to the right after each check until 'n' is 0.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n) — The number of iterations is proportional to the number of bits, which is log2(n).
Space Complexity: O(1) — Only a few variables are used.

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.

Convert the number to a binary string manually, store indices of '1's, calculate gaps, and keep track of the largest gap found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n)
Space Complexity: O(log n) due to storage of binary string.

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).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Convert to Binary and Find Gaps

Time Complexity: O(log n) — The number of iterations is proportional to the number of bits, which is log2(n).
Space Complexity: O(1) — Only a few variables are used.

Approach 2: String Conversion Method

Time Complexity: O(log n)
Space Complexity: O(log n) due to storage of binary string.

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Convert to Binary and Scan BitsO(log n)O(1)Best for interviews and optimal memory usage using bitwise operations
String Conversion MethodO(log n)O(log n)Simpler implementation when readability is preferred over strict space optimization

Video Solution

Binary Gap | Two Simple Approaches | Leetcode 868 | codestorywithMIK • codestorywithMIK • 4,754 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Binary Gap with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Two Integers

Next

Add Binary