Find the Missing Number

Given an array contains N numbers of 0 .. N, find which number doesn't exist in the array.

Example:

Given N = 3 and the array [0, 1, 3], return 2.

Solution:

We could use the Single Number's idea to solve this question.

• Calculate the xor sum from 0 to N
• Calculate the xor sum for all element in given array
• Xor these two sums

Code:

public class Solution {

    public int findMissing(int[] nums) {
        int x1 = 0;
        for (int i : nums) {
            x1 = x1 ^ i;
        }
        int x2 = 0;
        for (int i = 1; i <= nums.length; i++) {
            x2 = x2 ^ i;
        }
        return x1^x2;
    }
}