Problem

Given a positive integer N, find the longest distance (number of consecutive zeros) between two successive 1 bits in the binary representation of N. The distance is measured as the number of zeros between the two 1s.

Examples

Example 1

1
2
3

Input: N = 9  # binary 1001
Output: 2
Explanation: there are two zeros between the two 1s.
Similar Problems

Solution

Method 1 — Scan bits left-to-right (recommended)

Intuition

Traverse the binary representation from LSB to MSB (or vice versa). Track the position of the last seen 1 and when you encounter another 1, compute the gap between positions and update the maximum.

Approach

  • Initialize last = -1, maxGap = 0, and pos = 0.
  • While N > 0:
    • If (N & 1) == 1 and last != -1, update maxGap = max(maxGap, pos - last - 1).
    • If (N & 1) == 1, set last = pos.
    • Shift N >>= 1 and increment pos.
  • Return maxGap.

Edge cases:

  • If there are fewer than two 1 bits, the result is 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
 public:
  int binaryGap(int N) {
    int last = -1;
    int maxGap = 0;
    int pos = 0;
    while (N > 0) {
      if ((N & 1) == 1) {
        if (last != -1) maxGap = std::max(maxGap, pos - last - 1);
        last = pos;
      }
      N >>= 1;
      ++pos;
    }
    return maxGap;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

package main

func binaryGap(N int) int {
    last := -1
    maxGap := 0
    pos := 0
    for N > 0 {
        if (N & 1) == 1 {
            if last != -1 {
                gap := pos - last - 1
                if gap > maxGap { maxGap = gap }
            }
            last = pos
        }
        N >>= 1
        pos++
    }
    return maxGap
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  public int binaryGap(int N) {
    int last = -1;
    int maxGap = 0;
    int pos = 0;
    while (N > 0) {
      if ((N & 1) == 1) {
        if (last != -1) maxGap = Math.max(maxGap, pos - last - 1);
        last = pos;
      }
      N >>= 1;
      pos++;
    }
    return maxGap;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def binary_gap(self, N: int) -> int:
        last = -1
        max_gap = 0
        pos = 0
        while N > 0:
            if (N & 1) == 1:
                if last != -1:
                    max_gap = max(max_gap, pos - last - 1)
                last = pos
            N >>= 1
            pos += 1
        return max_gap

Complexity

  • ⏰ Time complexity: O(log N), proportional to the number of bits in N (we scan each bit once).
  • 🧺 Space complexity: O(1).

Method 2 — Use N & (N - 1) to iterate set bits (alternate)

Intuition

Iterate over the positions of set bits by repeatedly clearing the least-significant 1 using N &= (N - 1). Track the index of each cleared bit and compute gaps between successive set-bit positions.

Approach

  • Maintain prevPos = -1 and maxGap = 0.
  • While N > 0: find lsb = N & -N; compute currPos = trailingZeroCount(lsb) (index of that bit).
  • If prevPos != -1, update maxGap = max(maxGap, currPos - prevPos - 1).
  • Set prevPos = currPos and clear N &= (N - 1).

Note: trailingZeroCount can be implemented by counting shifts or using builtin intrinsics.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <bit>
class Solution {
 public:
  int binaryGapAlt(int N) {
    int prev = -1;
    int maxGap = 0;
    while (N > 0) {
      int lsb = N & -N;
      int pos = __builtin_ctz(lsb); // count trailing zeros
      if (prev != -1) maxGap = std::max(maxGap, pos - prev - 1);
      prev = pos;
      N &= (N - 1);
    }
    return maxGap;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

package main

import "math/bits"

func binaryGapAlt(N int) int {
  prev := -1
  maxGap := 0
  for N > 0 {
    lsb := N & -N
    pos := bits.TrailingZeros(uint(lsb))
    if prev != -1 {
      gap := pos - prev - 1
      if gap > maxGap { maxGap = gap }
    }
    prev = pos
    N &= (N - 1)
  }
  return maxGap
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public int binaryGapAlt(int N) {
    int prev = -1;
    int maxGap = 0;
    while (N > 0) {
      int lsb = N & -N;
      int pos = Integer.numberOfTrailingZeros(lsb);
      if (prev != -1) maxGap = Math.max(maxGap, pos - prev - 1);
      prev = pos;
      N &= (N - 1);
    }
    return maxGap;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:

  def binary_gap_alt(self, N: int) -> int:
    prev = -1
    max_gap = 0
    while N > 0:
      lsb = N & -N
      pos = (lsb.bit_length() - 1)
      if prev != -1:
        max_gap = max(max_gap, pos - prev - 1)
      prev = pos
      N &= (N - 1)
    return max_gap

Complexity

  • ⏰ Time complexity: O(k) where k is the number of set bits (worst-case O(log N)). Using bit intrinsics makes this efficient.
  • 🧺 Space complexity: O(1).

Notes

  • This problem appears on LeetCode as “Binary Gap” and on Codility under the same name; solutions above cover both platforms (differences are in input sizes/details only).
  • References preserved in source_links.