868. Binary Gap

UnknownView on LeetCode

Bit Manipulation

Time: O(log n)

Space: O(1)

Intuition

Find maximum distance between consecutive set bits in binary representation.

Algorithm

1Track position of previous set bit.
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.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

// 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?