[leetcode] missing number

problem

code

1st try: sorting

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i]) return i;
        }
        
        return nums.length;
    }
}

Time: O(NlogN)
Space: O(1)

2nd try: O(1) space, O(N) time

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

awsome to get this intuition!!!!!

3rd try with stream api

class Solution {
    public int missingNumber(int[] nums) {
        return IntStream.rangeClosed(0, nums.length).sum() - Arrays.stream(nums).sum();
    }
}

O(1) space, O(N) time

4th try with XOR

nums = [1, 2, 3] => missing 0
i: 0 - n => 0(i)^1(i)^1^2(i)^2^3(i)^3 = 0
why? 2^2 = 0

class Solution {
    public int missingNumber(int[] nums) {
      int missing = nums.length;
      // i: (0, nums.length - 1)
      // nums[i]: (0, nums.length) with a missing number (0, nums.length)
      // missing = nums.length, Σ i^nums[i]; i (0, nums.length - 1)
      for (int i = 0; i < nums.length; i++) missing ^= i^nums[i];
      return missing;
    }
}

O(1) space, O(N) time