leetcode 268 Missing Number
z
 2017-12-25 15:07:46  

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.

Example 1

1
2
3
Input: [3,0,1]
Output: 2

Example 2

1
2
3
Input: [9,6,4,2,3,5,7,0,1]
Output: 8

  • The sum of [0, 1, 2,..,n] should be n*(n+1)/2 , so the missing one could be calculated by n*(n-1)/2 minus the sum of array which exclude the missing array.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
        public int missingNumber(int[] nums) {
            int n = nums.length;
            int sum = 0;
            for(int i:nums){
                sum += i;
            }
            return n*(n+1)/2 - sum;
        }
    }

In the disscus area, there is an other solution using xor and ~ operation.

1
2
3
4
5
6
7
public int missingNumber(int[] nums) {
    int xor = 0, i = 0;
	for (i = 0; i < nums.length; i++) {
		xor = xor ^ i ^ nums[i];
	}
	return xor ^ i;
}
  • Notice that a xor b xor b = a
    • for example, let nums = [0,1,3]
    • xor = 0 xor 1 xor 3 xor 0 xor 1xor2 xor 3 = 2.
  • Notice that i should be initialized outside the for loop cause it will be used at the last return cause, outside the for loop.