LC268. Missing Number

class Solution:
    def missingNumber(self, A: List[int]) -> int:
        """ O(N) /O(1)
        1. get expected sum if A is sequence
        2. cnt actual sum
        3. the one missing is difference 
        
        """
        n = len(A)
        total = n*(n+1)//2
        actual = sum(A)
        return total - actual

class Solution:
    def missingNumber(self, A: List[int]) -> int:
        """ O(N) /O(1)
        main idea:  X ^ X = 0 and   value a in range   [0,N] and a is unique ,  =>   a-1  can supposedly find a index i, so (a-1) == idx  
        1. initialize res = len(A)
        2. XOR with all val and idx in the array
        3. return missing 
        
        """
        n = len(A)
        missing = n
        for i,a in enumerate(A):
            missing ^= a ^ i
        return missing