Binary Gap

LeetCode 899 | Difficulty: Easy

Easy

Problem Description

Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.

Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.

Example 1:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:

Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 3:

Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Constraints:

- `1 <= n <= 10^9`

Topics: Bit Manipulation

---

Approach

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 28 ms)

Metric	Value
Runtime	28 ms
Memory	25.4 MB
Date	2021-11-25

Solution

public class Solution {
    public int BinaryGap(int n) {
        int max = 0;
    int pos=0;
    int lastPos = -1;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            if (lastPos != -1)
            {
                max = Math.Max(max, pos-lastPos);
            }
            lastPos = pos;
        }
        n /= 2;
        pos++;
        
    }
    return max;
    }
}

📜 1 more C# submission(s)

Submission (2021-11-25) — 48 ms, 25.5 MB

public class Solution {
    public int BinaryGap(int n) {
        int max = 0;
    int d = -32;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            max = Math.Max(max, d);
            d = 0;
        }
        n /= 2;
        d++;
    }
    return max;
    }
}

---

Complexity Analysis

Approach	Time	Space
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.