Find Missing Number

Below is the one of the code using Xor

I've presented all the 5 techniques within the video description here

TL;DR

Question

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

All the numbers of nums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Solution

One of the approach is provided below

class Solution {
    /**
        x ^ 0 => x
        x ^ x => 0
     */
    public int missingNumber(int[] nums) {
        final int n = nums.length;
        // sum of n elements - sum of nums
        return xorOverRange(n) 
            ^ xorOverArray(nums);
    }

    int xorOverArray(int[] nums) {
        int xor = 0;
        for (int i = 0 ; i < nums.length; i++) {
            xor ^= nums[i];
        }
        return xor;
    }

    int xorOverRange(int n) {
        int xor = 0;
        for (int i = 0 ; i <= n; i++) {
            xor ^= i;
        }
        return xor;
    }
}

For more different approach, checkout the video mentioned above.