Twitter Codility Problem - Max Binary Gap

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

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

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

C++

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;
  }
};

Go

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
}

Java

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;
  }
}

Python

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

C++

#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;
  }
};

Go

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
}

Java

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;
  }
}

Python

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.