868. Binary Gap

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⁹

Submitted Code

class Solution(object):
    def binaryGap(self, n):
        """
        :type n: int
        :rtype: int
        """
        idx = 0             # 현재 자리수의 인덱스
        prev = None         # 이전 1비트의 인덱스
        max_distance = 0

        while n != 0:
            if n & 1 == 1:
                if prev is None:
                    prev = idx
                else:
                    max_distance = max(max_distance, (idx - prev))
                    prev = idx
            
            n >>= 1
            idx += 1
        
        return max_distance

Runtime: 0 ms | Beats 100.00%
Memory: 12.49 MB | Beats 52.54%

& 와 » 연산자로 뒤에서부터 1비트씩 검사하고, 인덱스를 붙여 거리를 계산했다.

Other Solutions

1st

    def binaryGap(self, N):
        index = [i for i, v in enumerate(bin(N)) if v == '1']
        return max([b - a for a, b in zip(index, index[1:])] or [0])

time complexity: 𝑂(log𝑛) ← n의 비트 수
space complexity: 𝑂(log𝑛)

파이썬 내장 함수를 통해 정수를 이진 문자열로 변환해서 풀 수도 있지만 공간 효율성은 비트를 직접 연산하는 것보다 떨어진다.

n = 22

bin(N) = "0 b 1 0 1 1 0"
index  = [    2,  4,5  ]

                          a  b    a  b
zip(index, index[1:]) → [(2, 4), (4, 5)]
                b - a →     2       1
                           max

return 2