Description:
https://leetcode.com/problems/missing-number/#/description
Algorithm:
- Use sum as shown in Code1.
- Use XOR
Code1:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution1 { public: int missingNumber(vector& nums) { int sumAll = 0; int sum = 0; for (int i = 0; i < nums.size() + 1;i++) sumAll += i; for (int i = 0; i < nums.size();i++) sum += nums[i]; return sumAll - sum; } }; |
Code2:
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int missingNumber(vector& nums) { int res = nums.size(); for (int i = 0; i < nums.size(); i++) { res ^= nums[i]; //xor res ^= i; } return res; } }; |
Time & Space:
O(n) & O(1)