268

268. Missing Number (Easy)

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?

Related Topics:
Array, Math, Bit Manipulation

Similar Questions:

• First Missing Positive (Hard)
• Single Number (Easy)
• Find the Duplicate Number (Medium)
• Couples Holding Hands (Hard)

Solution 1. Sum of Arithmetic Sequence

// OJ: https://leetcode.com/problems/missing-number/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int missingNumber(vector<int>& A) {
        return (1 + A.size()) * A.size() / 2 - accumulate(begin(A), end(A), 0);
    }
};

Solution 2. XOR

// OJ: https://leetcode.com/problems/missing-number/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size(), xorVal = 0;
        for (int i = 0; i < n; ++i) xorVal ^= nums[i] ^ (i + 1);
        return xorVal;
    }
};