LeetCode [268] Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

class Solution { public: int missingNumber(vector<int>& nums) { int ret = 0; for(auto n:nums) ret ^= n; for(int i=1; i<=nums.size(); ++i) ret ^= i; return ret; } }; class Solution { public: int missingNumber(vector<int>& nums) { int n = 0, m = INT_MIN;//n = xor of all existing numbers, m is the maximum for(auto i:nums){ n ^= i; m = max(m, i); } if(m!=nums.size()) return nums.size(); int m1 = m, w = 0;//w is #digits in m. eg., m=1010 w = 4 while(m1){ w++; m1 >>= 1; } int ret = 0; for(int i=w; i>0; --i){ int t = pow(2,i-1), k = 0; //k=1 if the count of 1s on i-th digit of all numbers (including the missing number) if(i==1) k = ((m+1)/2%2); else if(m%(t*2)>=t) k = (m%t+1)%2; int p = (n&t)>>(i-1);//i-th digit of n ret |= ((k^p)*t); } return ret; } }; class Solution { public: int missingNumber(vector<int>& nums) { int miss = 0; for(int i=0; i<nums.size(); ++i){ miss ^= ((i+1)^nums[i]); } return miss; } }; class Solution { public: int missingNumber(vector<int>& nums) { int n = nums.size(); int sum_miss = accumulate(nums.begin(), nums.end(), 0); int sum_all = (1+n)*n/2; return sum_all - sum_miss; } }; class Solution{ public: int getDupSum(vector<int> nums){ int n = nums.size()-1; return accumulate(nums.begin(), nums.end(), 0)-(1+n)*n/2; } int getDupBit(vector<int> nums){ int ret = 0, n = nums.size()-1; for(int i=0; i<n; ++i){ ret ^= ((i+1)^(nums[i])); } return ret^nums[n]; } };

1 2 3 4 5 6 7 8 9

//Java class Solution { public int missingNumber(int[] nums) { int s = 0; for(int v:nums) s+=v; int n = nums.length; return n*(n+1)/2-s; } }