[Leetcode] 201. Bitwise AND of Numbers Range

initial

according to my test cases, it is the MSB that determines the common prefix. So I did like

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        # 101
        # 110
        # 111
        # ====
        # 100

        # 0110
        # 0111
        # 1000
        # ====
        # 0000

        # 0111
        # 1000
        # 1001
        # 1010
        # =====
        # 0000

        def find_msb(num):
            count=0

            while num>=1:
                num = num>>1
                count+=1
            return count

        leftMSB,rightMSB = find_msb(left),find_msb(right)
        if leftMSB==0:
            return 0
        elif leftMSB==rightMSB:
            return 1<<(leftMSB-1)
        else:
            return 0

        

sol

but actually if we have

left = 416  (0b110100000)
right = 436 (0b110110100).

we can see that the common prefix is 1101. It is not just the MSB of 1.

So we have to iterate through left and right simultaneously. What i mean is each iteration should right shift left and right to delete the LSB. Also while doing that we should increment the depth.

Once left==right, we left shift our left value by the depth to get the prefix.

actually i did like

        count=0
        while left>=1 and right>=1:
            if left!=right:
                left>>=1
                right>>=1
                count+=1
            else:
                break
        return left<<count

but u can just do

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        """
        Calculates the bitwise AND of all numbers in the range [left, right], inclusive.

        This is done by finding the longest common prefix of the binary representations
        of 'left' and 'right'. Any bits to the right of this common prefix will
        eventually become 0 due to the AND operation across the range.
        """
        
        # 'shift_count' will keep track of how many times we right-shifted
        shift_count = 0
        
        # While 'left' and 'right' are not equal, keep shifting them both to the right.
        # This process effectively removes the differing least significant bits
        # until only the common prefix remains.
        while left != right:
            left >>= 1   # Right shift left by 1 bit
            right >>= 1  # Right shift right by 1 bit
            shift_count += 1 # Increment the count of shifts
            
        # Once left == right, 'left' (or 'right') holds the longest common prefix
        # of the original 'left' and 'right' numbers.
        # To get the final result, we need to shift this common prefix back
        # to its original position by left-shifting it by 'shift_count'.
        # This effectively appends '0's for all the bits that were removed
        # and would have become 0 in the bitwise AND.
        return left << shift_count

complexity

msb of right is time? cuz we iterate by that much
1 space

time is wrong.

The maximum number of right shifts you can perform on a number N before it becomes 0 is roughly equal to its number of bits (log n).
but thisi s what i meant like how many bits right has

Therefore, the time complexity is O(K), where K is the number of bits (a constant like 32 or 64). This is equivalent to O(log(max(left, right))).