268. Missing Number

Description:

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

 

'''
[1] two pass)

idea::
[0,n] -> exclusive XOR -> ans
ans-> for num in nums: ans^=num -> ans

-T/C: O(n+1 + n) =O(2n) =O(n)
-S/C: O(1)
'''
'''
[2] one pass)

idea::
while XOR operation in nums, also do XOR opeartion j.
after loop, ans^=j. then return ans

code::
(below)

-S/C: O(n+1)=O(n)
-T/C: O(1)
'''
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        j=0;
        ans=0;
        for num in nums:
            ans=ans^num^j
            j+=1
        ans^=j
        return ans