## Algorithm

Problem Name: 868. Binary Gap

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 <= 109`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int binaryGap(int n) {
int lastOnePosition = -1;
int currPosition = 0;
int maxGap = 0;
while (n > 0) {
int rem = n % 2;
n /= 2;
if (rem == 1) {
if (lastOnePosition != -1) {
maxGap = Math.max(maxGap, currPosition - lastOnePosition);
}
lastOnePosition = currPosition;
}
currPosition++;
}
return maxGap;
}
}
``````
Copy The Code &

Input

cmd
n = 22

Output

cmd
2

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const binaryGap = function(N) {
const bin = (N >>> 0).toString(2);
const idxArr = [];
for (let i = 0; i < bin.length; i++) {
const num = bin.charAt(i);
if (num === "1") {
idxArr.push(i);
}
}
let maxConLen = 0;
for (let idx = 0; idx < idxArr.length - 1; idx++) {
if (idxArr[idx + 1] - idxArr[idx] > maxConLen) {
maxConLen = idxArr[idx + 1] - idxArr[idx];
}
}

return maxConLen;
};
``````
Copy The Code &

Input

cmd
n = 22

Output

cmd
2

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def binaryGap(self, N):
pre = dist = 0
for i, c in enumerate(bin(N)[2:]):
if c == "1":
dist = max(dist, i - pre)
pre = i
return dist
``````
Copy The Code &

Input

cmd
n = 8

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0868_BinaryGap
{
public int BinaryGap(int N)
{
var last = -1;
var result = 0;
for (int i = 0; i < 32; i++)
{
if (((N >> i) & 1) == 1)
{
if (last >= 0)
result = Math.Max(result, i - last);
last = i;
}
}

return result;
}
}
}
``````
Copy The Code &

Input

cmd
n = 8