class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # To attempt this problem, first think of traversing from the end
        # then it is easy to realise we only need to pick the larger of the two choices (i,j)
        # and put it at current position(k). if we pick i, decrement i, otherwise we picked j so 
        # decrement j. That's it!
        i = m - 1
        j = n - 1
        k = m + n - 1
        
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
 

 
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # in place removal requires shifting. Or just skipping!
        # keep a hare (i) and a tortoise (k) and instead of checking 
        # if nums[i] == val, check the opposite, or nums[i] != val, then  
        # set nums[tortoise] = nums[hare]. It will skip when nums[hare] == val
        k = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
        return k
 

 
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # Same hare and tortoise routine!            
        # check from the end, check each element
        # if previous value is same as current value
        # pop the current value     
        k = len(nums) - 1
        for i in nums[::-1]:
            if i == nums[k - 1] and k > 0:
                nums.pop(k)
            k -= 1
        return len(nums)
 

 
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # This problem can be solved using hashmap and a counter
        # but O(1) space? The majority element can be appearing at 
        # least 2 times, so we can keep a counter and ++ / -- it
        # upon seeing it again. If majority element occures even times (>=2),
        # we save it in result = i, if odd times (>=3), we don't update as it 
        # will have been updated during 2nd occurance    
        count = 0
        result = 0
        for i in nums:
            if count == 0:
                result = i
            if i == result:
                count += 1
            else:
                count -= 1

        return result
 

 
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0): 
            return False
        
        original = x
        reverted = 0
        while x != 0:
            reverted = reverted * 10 + x % 10
            x //= 10

        return original == reverted
 

 
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        i = len(digits) - 1
        while i >= 0:
            if digits[i] == 9:
                digits[i] = 0
                i -= 1
            else:
                digits[i] += 1
                return digits
                
        return [1] + digits
 

 
class Solution:
    def trailingZeroes(self, n: int) -> int:
        return n // 5 + self.trailingZeroes(n // 5) if n else 0
 

 
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2: 
            return x
        lo, hi = 2, x // 2
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            sqr_mid = mid*mid
            if sqr_mid < x:
                lo = mid + 1
            elif sqr_mid > x:
                hi = mid - 1
            else: 
                return mid
        return hi
 

 
class Solution:
    def binaryExp(self, x: float, n: int) -> float:
        if n == 0:
            return 1

        if n < 0:
            n = -1 * n
            x = 1.0 / x

        result = 1
        while n != 0:
            # x ^ (n+1) = x^n * x
            if n % 2 == 1:
                result *= x
                n -= 1
            # x^n = (x^2)^(n/2)
            x *= x
            n //= 2
        return result

    def myPow(self, x: float, n: int) -> float:
        return self.binaryExp(x, n)
                        
 

 
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 2:
            return len(points)

        def find_slope(p1, p2):
            x1, y1 = p1
            x2, y2 = p2
            if x1 - x2 == 0:
                return inf
            return (y1 - y2) / (x1 - x2)

        ans = 1
        for i, p1 in enumerate(points):
            slopes = defaultdict(int)
            for j, p2 in enumerate(points[i + 1:]):
                slope = find_slope(p1, p2)
                slopes[slope] += 1
                ans = max(slopes[slope] + 1, ans)
        return ans
                
 

 
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        # to remove '0b' from answer, use [2:]    
        return bin(x)[2:]
 

 
class Solution:
    def reverseBits(self, n: int) -> int:
        ret, power = 0, 31
        while n:
            ret += (n & 1) << power
            n = n >> 1
            power -= 1
        return ret
                
 

 
class Solution:
    def hammingWeight(self, n: int) -> int:
        c = 0
        while n:
            c += (n&1)
            n >>= 1
        return c
 

 
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = 0
        for i in nums:
            a = a ^ i
        return a
 

 
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # bit masking is about setting, clearing and toggling bits
        # so don't get lost in problem. you are setting bits / making numbers
        a, b = 0, 0
        mask = 0
        for i in nums:
            # if a(current) == i(current), we saw it twice; once in i another in a
            # we keep common bits using &
            # we store bits using |
            b |= a & i
            # if a(previous) == i(current) and vice versa, we toggle a accordingly
            # we toggle using ^
            a ^= i
            # if an element appears three times, we will find it in b (twice) 
            # and a (third time) both. So in case something appears three times, we
            # remove it both from a and b
            mask = (a & b)
            a &= ~mask
            b &= ~mask
        # a holds only the number (bits) which was not repeated three times
        return a
                
 

 
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        # the trick of this problem is understanding common prefix
        # a common prefix is needed because of how & resets a bit if any operand 
        #  is a zero bit. So we can shift right until we hit 1s for both as long as 
        #  left < right, and as we keep shifting right, we keep count. Finally we 
        #  left shift 'left'/'right' to produce the actual prefix  
        count = 0
        while left < right:
            left >>= 1
            right >>= 1
            count += 1
        return right << count