# 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 = 22Output: 2Explanation: 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 = 8Output: 0Explanation: 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 = 5Output: 2Explanation: 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)

--

-- ## Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.