class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        sum = len(nums) * （len(nums) + 1）/ 2
        for i in range(len(nums)):
            sum -= nums[i]
            
        return sum

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        miss = len(nums)
        
        for i in range(len(nums)):
            miss ^= i ^ nums[i]
            
        return miss

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        s = list(s)
        t = list(t)
        s.sort()
        t.sort()
        for i in range(len(s)):
            if s[i] != t[i]: return False
            
        return True

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        dic1, dic2 = [0]*26, [0]*26
        
        for i in range(len(s)):
            dic1[ord(s[i]) - ord('a')] += 1
            dic2[ord(t[i]) - ord('a')] += 1
            
        return dic1 == dic2
            

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return True
            
        return False

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        s = set()
        for num in nums:
            if num in s: return True
            else: s.add(num)
            
        return False

 class Solution:
    def countPrimes(self, n: int) -> int:
        
        if n < 3: return 0
        
        s = [1] * n
        s[0] = 0
        s[1] = 0
        
        #first one is i*i, thus when i*i > n will do nothing.
        for i in range(2,int(n ** 0.5) + 1): 
            if s[i] == 1:
                #As (i-1)*i is already marked in the previous case of i-1, so we can start from i*i
                s[i*i:n:i] = [0] * len(s[i * i:n:i])
            
        return sum(s)
    
    

    
       #O[n*(1+1/2+1/3+1/4+1/5+1/6+…1/int(n ** 0.5) + 1))]

class Solution:
    def isHappy(self, n: int) -> bool:
        ans = 0
        start = n
        sums = set()
        while n not in sums and ans != 1:     
            sums.add(n)
            ans = self.sumofsquares(n)
            n = ans            
        return ans == 1   
            
            
    def sumofsquares(self, n) -> int:
        s = 0
        while n > 0:
            s += (n % 10) ** 2
            n = n // 10
        return s

class Solution:
    def isHappy(self, n: int) -> bool:

        sums = set()
        while n not in sums:
            sums.add(n)
            n = sum(int(i)**2 for i in str(n))
        return n == 1

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
            
        ans = 0
        for i in range(32):
            ans += (n & 1)
            n = n >> 1
        return ans

n: xxxxxxxx1 ans = 0
n-1: xxxxxxx0
n = n&(n-1): xxxxxxx10 xxx(n of 0) ans = 1 (one 1)
n-1: xxxxxxx01 or xxx0(n of 1)
n = n&(n-1): xxxxxxx00 or xxx(n of 0) ans = 2 (one 1)
untile
n = 0

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
            
        ans = 0
        while n:
            ans += 1
            n &= (n - 1)
        return ans

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        
        ans = 0
        for i in range(32):
            ans = (ans << 1) + (n & 1)
            n >>= 1
            
        return ans

class Solution:
     def rotate(self, nums: List[int], k: int) -> None:
         """
         Do not return anything, modify nums in-place instead.
         """
         tmp = []
         tmp[:k] = nums[len(nums)-k:]
         tmp[k:] = nums[:len(nums)-k]
         for i in range(len(nums)):
             nums[i] = tmp[i]

 Cass Solution:
     def rotate(self, nums: List[int], k: int) -> None:
         """
         Do not return anything, modify nums in-place instead.
         """
         nums[:] = nums[len(nums)-k:] + nums[:len(nums)-k] 

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        k = k % len(nums)
        self.reverse(nums, 0, len(nums) - 1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, len(nums) - 1)
        
    def reverse(self, nums: List[int], x: int, y: int) -> None:
        while x < y:
            tmp = nums[x]
            nums[x] = nums[y]
            nums[y] = tmp
            x += 1
            y -= 1

class Solution:
    def trailingZeroes(self, n: int) -> int:
        
        ans = 0
        
        while n > 0:
            ans += n // 5
            n = n // 5
            
        return ans