Binary Gap

Easy
418.

Binary Gap

Binary Gap is an easy coding problem on bit manipulation, asked in Amazon, Google and Twitter interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var binaryGap = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Walk the bits from least significant to most significant, tracking the position of the previous 1.

  2. Hint 2

    On each new 1, the distance is the current position minus that remembered one.

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

  1. For each bit index, if the bit is set and a previous 1 exists, update best with the gap; record the index.
  2. 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 best

Java

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