Link: https://leetcode.com/problems/missing-number/

Constraints:

    n == nums.length
    1 <= n <= 104
    0 <= nums[i] <= n
    All the numbers of nums are unique.

Idea

Use a boolean array to keep track of whether a number is present in the given array. If a number n present, the entry at position n of the boolean array should be set to true.

Code

• Solution 1

class Solution {
    public int missingNumber(int[] nums) {
        boolean[] numberPresent = new boolean[nums.length + 1];
        for (int n : nums) {
            numberPresent[n] = true;
        }
        
        for (int i = 0; i < numberPresent.length; i++) {
            if (!numberPresent[i]) {
                return i;
            }
        }
        
        return -1;
    }
}

• Time: O(n). First pass to scan the nums array. The second pass is to scan the boolean array.

• Space: O(n) as we are using a boolean map of size (n + 1).

• Solution 2
  Since all the numers are unique and within the range of [0, n], we could use arithmetric sequence formula to get the missing number.

class Solution {
   public int missingNumber(int[] nums) {
       int n = nums.length;
       int sumOfNumsInRange = n * (n + 1) / 2;
       int sumOfNumsInArray = 0;
       for (int e : nums) {
           sumOfNumsInArray += e;
       }
       
       return sumOfNumsInRange - sumOfNumsInArray;
   }
}

• Time: O(n).

• Space: O(1).

• Solution 3 (bit manipulation)

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