DDSA Solutions

868. Binary Gap

UnknownView on LeetCode
Bit Manipulation
Time: O(log n)
Space: O(1)

Problem Overview

Find maximum distance between consecutive set bits in binary representation.

Intuition

Find maximum distance between consecutive set bits in binary representation.

Algorithm

  1. 1Track position of previous set bit.
  2. 2Iterate through bits: when set bit found, update max gap with current_pos - prev_pos. Set prev_pos = current_pos.

Example Walkthrough

Input: n=22 (10110)

  1. 1.Set bits at positions 1,2,4. Gaps: 1,2. Max=2.

Output: 2

Common Pitfalls

  • •If only one set bit, return 0.
868.cs
C#
// Approach: Single pass through bits; track the distance from the last seen set bit and update the maximum.
// Time: O(log n) Space: O(1)

public class Solution
{
    public int BinaryGap(int n)
    {
        int ans = 0;

        // d := the distance between any two 1s
        for (int d = -32; n > 0; n /= 2, ++d)
        {
            if (n % 2 == 1)
            {
                ans = Math.Max(ans, d);
                d = 0;
            }
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems