# 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`

*Approach 1:*

*Using a list to store index position of 1's*

Convert the number to the binary format . Then iterate over the binary string. If the value is 1 then add the index position to the list. After traversing the entire string. Calculate the required max distance using the list created.

**Time : O(logn)**

**Space: O(logn)**

*Approach 2:*

*By storing previous position where a 1 is found*

While on iteration on the binary string , we will store the indexes , where a ‘1' is found and when current position also is found to have a 1 , we will be calculating the distance, by the formula (prev -current), if this current distance is greater than maximum distance found so far, then we will have to update the maximum distance variable by the new distance.

**Time : O(logn)**

**Space: O(1)**

*Approach 3:*

The same solution above can be implemented in a different way by using it operation , rather than creating a binary string

`class Solution:`

def binaryGap(self, n: int) -> int:

prev,i,max_=-1,0,0

while(n>0):

if(n&1==1):

if prev>=0:

max_=max(max_,i-prev)

prev=i

n>>=1

i+=1

return(max_)

**Time : O(logn)**

**Space: O(1)**