2.2 Missing Number

Description

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

For example, Given nums = [0, 1, 3] return 2.

Method

method 1: bit manipulation XOR(^) method 2: bucket sort method 3: sum

Time and Space Complexity

for 1: o(n) for 2: o(n + (n + 1)) for 3 : o (n)

Code

for 1: public class Solution {

public int missingNumber(int[] nums) {
       if (nums == null || nums.length == 0){
          return 0;
      }
      int n = nums.length;
      int all = 0;
      int arrRes = 0;
      for (int i = 0; i < n; i++){
          all ^= i;
          arrRes ^= nums[i];
      }
      all ^= n;
      int res = all ^ arrRes;
      return res;
}

} for 2: public class Solution {

public int missingNumber(int[] nums) {
       if (nums == null || nums.length == 0){
           return 0;
       }
       int n = nums.length;
       int[] arr = new int[n + 1];
       Arrays.fill(arr, -1);
       for (int i = 0 ; i < n; i++){
            arr[nums[i]] = nums[i];
       }
       for (int i = 0; i <= n; i++){
           if (arr[i] == -1){
               return i;
           }
       }
       return 0;
}

}