201. Bitwise AND of Numbers Range

[zeikar]

Problem link

https://leetcode.com/problems/bitwise-and-of-numbers-range

Problem Summary

left, right가 주어질 때 [left, right] 사이의 모든 수에 대해 AND 연산을 한 값을 구하는 문제.

Solution

AND 연산의 특성 상 0이 하나라도 있으면 다 0이 된다.
즉, left, right 둘 간의 prefix를 찾으면 그 뒤로는 전부 0이 될 것이다. 그래서 left, right의 공통 prefix를 찾으면 되는데... 처음에 이걸 좀 더럽게 구현했다.

ChatGPT나 솔루션을 보니 left, right가 같아질 때까지 오른쪽으로 shift, 같아지면 그때 shift한 횟수만큼 다시 왼쪽으로 shift 해서 prefix를 깔끔하게 구하더라. 물론 시간복잡도는 log(n)이니... 큰 상관은 없긴 하다

Source Code

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        res = 0
        check = (1 << 31)
        while check > 0:
            if (left & right & check) == check:
                res += check
            elif (left & check) != (right & check):
                break
            check >>= 1

        return res