Missing Number

Problem Statement

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Link to GitHub code


Example,
Given nums = [0, 1, 3] return 2



Solution

• 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.

package Algorithms.Arrays;

public class MissingNumber {
 public static int get(int []arr)
 {
  int xor=0, i=0;
  
     for(i=0;i<arr.length;i++)
     {
      xor=xor ^ i ^ arr[i];
     }
     return xor ^ i;
  
 }

}

Iteration