Binary Gap — Solution in Python, Java & C++
Binary Gap solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Google.
Binary Gap is an easy coding problem on bit manipulation, asked in Amazon, Google and Twitter interviews.
- Difficulty: Easy
- Topics: Bit Manipulation
- Asked at: Amazon, Google, Twitter
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a positive integer n, return the longest distance between any two adjacent 1 bits in its binary representation. If there are fewer than two 1 bits, return 0.
Two 1 bits are adjacent when only 0 bits lie between them; the distance is the difference of their positions.
Example 1
Input: n = 22
Output: 2
Explanation: 10110 — the gaps are 2 and 1.
Example 2
Input: n = 8
Output: 0
Explanation: 1000 has a single 1 bit.
Example 3
Input: n = 5
Output: 2
Constraints
1 <= n <= 1000000000
Hints for Binary Gap
Hint 1
Walk the bits from least significant to most significant, tracking the position of the previous
1.Hint 2
On each new
1, the distance is the current position minus that remembered one.Hint 3
Keep the maximum; a number with one set bit never records a distance, so it returns 0.
How to solve Binary Gap
Walk the bits tracking the position of the previous 1; each new 1 yields a distance.
Approach
- For each bit index, if the bit is set and a previous 1 exists, update
bestwith the gap; record the index. - Return
best.
Why it works
Adjacent 1s are consecutive set bits, so the gap between each consecutive pair is measured exactly once.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
- A single set bit never records a distance and correctly returns 0.
Reference solution
Python
def binaryGap(n: int) -> int:
best = 0
last = -1
index = 0
while n:
if n & 1:
if last >= 0:
best = max(best, index - last)
last = index
n >>= 1
index += 1
return bestJava
public static int binaryGap(int n) {
int best = 0, last = -1, index = 0, v = n;
while (v > 0) {
if ((v & 1) == 1) {
if (last >= 0) best = Math.max(best, index - last);
last = index;
}
v >>= 1;
index++;
}
return best;
}C++
int binaryGap(int n) {
int best = 0, last = -1, index = 0, v = n;
while (v > 0) {
if (v & 1) {
if (last >= 0) best = max(best, index - last);
last = index;
}
v >>= 1;
index++;
}
return best;
}JavaScript
var binaryGap = function(n) {
let best = 0;
let last = -1;
let index = 0;
let v = n;
while (v > 0) {
if (v % 2 === 1) {
if (last >= 0 && index - last > best) best = index - last;
last = index;
}
v = Math.floor(v / 2);
index++;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 146 bit manipulation problems · the whole catalogue
Learn the technique: Bit Manipulation