LeetCode 268. Missing Number
Created at 2017-11-03 Updated at 2017-11-07 Category LeetCode
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Given nums = [0, 1, 3] return 2.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Since there are
n values taken from
0, 1, 2, ..., n , we can use
xor to get the missing value, for example if
n equals 3, then the raw values are
0, 1, 2, 3, and the
nums for example is
0, 2, 3. If you do
xor operation on each item in raw values and nums one by one.