# Share four different solutions

• // sort + binary seach
// O(nlogn) time, O(1) space
int missingNumber1(vector<int>& nums) {
sort(nums.begin(), nums.end());
int m = 0;
int l = 0, r = nums.size() - 1;
while (l < r) {
m = (l + r ) / 2;
if (nums[m] == m) l = m + 1;
else r = m - 1;
}

return nums[l] == l ? l + 1 : l;
}

// arithmetic progression
// O(n) time, O(1) space
int missingNumber2(vector<int>& nums) {
int sum1 = 0;
for (int x : nums) sum1 += x;
int minV = 0, maxV = nums.size();
int sum2 =  (minV + maxV) * (nums.size() + 1) / 2;
return sum2 - sum1;
}

// XOR
// O(n) time, O(1) space
int missingNumber3(vector<int>& nums) {
int ans = 0;
for (int i = 0; i <= nums.size(); ++i)
ans ^= (i == nums.size()) ? i : i ^ nums[i];
return ans;
}

// map table
// O(n) time, O(1) space
int missingNumber(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
while (nums[i] != i && nums[i] < nums.size() && nums[i] != nums[nums[i]])
swap(nums[i], nums[nums[i]]);
}

for (int i = 0; i < nums.size(); ++i)
if (nums[i] != i) return i;

return nums.size();
}

• If you are using sort() method, how come it would be O(n) linear time?

• that's O(nlgn) time, i have written it on the comment

• In the fourth solution, why did you add condition "nums[i] != nums[nums[i]]"? I believe this condition always holds.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.