forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_gap.py
More file actions
27 lines (26 loc) · 767 Bytes
/
binary_gap.py
File metadata and controls
27 lines (26 loc) · 767 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
Given a positive integer N, find and return the longest distance between two
consecutive 1' in the binary representation of N.
If there are not two consecutive 1's, return 0
For example:
Input: 22
Output: 2
Explanation:
22 in binary is 10110
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2
"""
def binary_gap(N):
last = None
ans = 0
index = 0
while N != 0:
if N & 1:
if last is not None:
ans = max(ans, index - last)
last = index
index = index + 1
N = N >> 1
return ans