LeetCode Q268: 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?

Solution:

	class Solution {
	public:
	int missingNumber(vector<int>& nums) {
	int minv=nums[0];
	int maxv=nums[0];
	int sum=0;
	for(int i=0; i<nums.size(); i++){
	if(nums[i]<minv) minv=nums[i];
	if(nums[i]>maxv) maxv=nums[i];
	sum+=nums[i];
	}
	if(minv!=0)
	return 0;
	if(maxv-minv+1==nums.size())
	return maxv+1;
	int sum1 = (1+nums.size())*(minv+maxv)/2;
	return sum1-sum;
	}
	};

view raw Q268.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int missingNumber(vector<int>& nums) {
	int n= nums.size()+1;
	int targetSum = (n-1)*n/2;
	int realSum = 0;
	for(int i=0; i<nums.size(); i++)
	realSum+=nums[i];
	return targetSum-realSum;
	}
	};

view raw Q268Rnd2.cpp hosted with ❤ by GitHub

Round 3 solution:

	class Solution {
	public:
	int missingNumber(vector<int>& nums) {
	int result = nums.size();
	int i=0;
	for(int num:nums){
	result ^= num;
	result ^= i;
	i++;
	}
	return result;
	}
	};

view raw Q268Rnd3.cpp hosted with ❤ by GitHub