# 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.

For example,
Given nums = `[0, 1, 3]` return `2`.

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

``````class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum = 0, n = nums.size();
for (auto &a : nums) {
sum += a;
}
return 0.5 * n * (n + 1) - sum;
}
};
``````

``````class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = 0;
for (int i = 0; i < nums.size(); ++i) {
res ^= (i + 1) ^ nums[i];
}
return res;
}
};
``````

``````class Solution {
public:
int missingNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > mid) right = mid;
else left = mid + 1;
}
return right;
}
};
``````

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation