jinhuang1102

268. Missing Number

Jan 18th, 2019
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.86 KB | None | 0 0
  1. """
  2. Because we know that nums contains nn numbers and that it is missing exactly one number on the range [0..n-1][0..n−1], we know that nn definitely replaces the missing number in nums. Therefore, if we initialize an integer to nn and XOR it with every index and value, we will be left with the missing number. Consider the following example (the values have been sorted for intuitive convenience, but need not be):
  3.  
  4. Index   0   1   2   3
  5. Value   0   1   3   4
  6. missing = 4∧(0∧0)∧(1∧1)∧(2∧3)∧(3∧4)
  7.         = (4∧4)∧(0∧0)∧(1∧1)∧(3∧3)∧2
  8.         = 0∧0∧0∧0∧2=2
  9. """
  10.  
  11.  
  12. class Solution(object):
  13.     def missingNumber(self, nums):
  14.         """
  15.        :type nums: List[int]
  16.        :rtype: int
  17.        """
  18.         missing = len(nums)
  19.         for i in range(0, len(nums)):
  20.             missing = missing ^ i ^ nums[i]
  21.            
  22.         return missing
Advertisement
Add Comment
Please, Sign In to add comment