Bitwise AND of Numbers Range | Brian Kernighan | LeetCode | Solution Explained
201. Bitwise AND of Numbers Range. Would have been easy if we were allowed to iterate over all the values. But, we have to be smarter and think in terms of bits. Finally, we discuss how to use Brian Kernighan algorithm. Problem Link.
Brute force Solution (Time Limit Exceeded)
class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: ans = left for i in range(left, right+1): ans &= i if not ans: return ans return ans
Nis the number of numbers between
right. This is
2**31-1, which will go out of limits.
O(1)since we are only storing the
Since the question is in the terms of bits, it is a good idea to think in terms of bits. Let’s see what happens here:
We figure that if there is at least 1 zero in the specified column, the entire column results in the value 0. ONLY if all the values are the same – either 1s or 0s in the column, then we keep it as is. Let’s take a look at another example.
It looks as if we are looking for the first disagreement between the
Solution 1. Bit Shift (Accepted)
class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: ans = 0 for bit in reversed(range(31)): if ((1 << bit) & left) == ((1 << bit) & right): ans |= ((1 << bit) & left) else: break return ans
Solution 2. Setting to 0s (Accepted)
Alternatively, we can go in the reverse direction and keep setting the ith bit 0, bit by bit – until
left > right
class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: bit = 0 while left < right: right = right & ~(1 << bit) bit += 1 return right
Solution 3. Brian Kernighan’s Algorithm (Accepted)
A smarter way to set the last set bit to zero is to do
num & (num-1) since that is going to convert the 1 – the set bit to a 0. This way we are able to skip over some bits, making this approach a bit faster.
class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: while left < right: right = right & (right - 1) return right
O(1)since we have to go over 31 bits at maximum
O(1)since we are storing only the
ansin solution 1 and 2 and nothing in solution 3
Thanks for reading!
June 13, 2022
June 13, 2022
January 24, 2022