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?
public class Solution {
public int MissingNumber(int[] nums) {
int len = nums.Length;
int expectedSum = len*(len+1)/2;
int sum = 0;
for(int i=0;i<nums.Length;i++){
sum+=nums[i];
}
return expectedSum - sum;
}
}Time Complexity: O(n)
Space Complexity: O(1)
