268. Missing Number

Given an array containingndistinct numbers taken from0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Givennums=[0, 1, 3]return2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Credits:
Special thanks to@jianchao.li.fighterfor adding this problem and creating all test cases.

Thought

XOR

OP1    OP2    RES
0      0      0
0      1      1
1      0      1
1      1      0

e.g.,

    1    1    0    1
 ^  1    1    0    0
    ----------------
    0    0    0    1

Solution

REF. 4 Line Simple Java Bit Manipulate Solution with Explaination by mo10

The basic idea is to use XOR operation. We all know that a^b^b =a, which means two xor operations with the same number will eliminate the number and reveal the original number.

In this solution, I apply XOR operation to both the index and value of the array. In a complete array with no missing numbers, the index and value should be perfectly corresponding( nums[index] = index), so in a missing array, what left finally is the missing number.

public class Solution {
    public int missingNumber(int[] nums) {
        int xor = 0, i;
        for (i = 0; i < nums.length; i++) {
            xor = xor ^ i ^ nums[i];
        }

        return xor ^ i;
    }
}