[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;
    }
}

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;
    }
}

3rd try with stream api

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

4th try with XOR

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;
    }
}