Wednesday, June 7, 2017

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

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


  • 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;
      xor=xor ^ i ^ arr[i];
     return xor ^ i;



No comments:

Post a Comment