Problem

Problem_Link

Solution (time, space)

1. Math (Sum of Integers Formula) O(n), O(1)
2. Hashing O(n), O(n)
3. XOR Bit Manipulation O(n), O(1)

Math (Sum of Integers Formula) O(n), O(1)

class Solution {
    public int missingNumber(int[] nums) {

        int n = nums.length;
        int expectedSum=(n*(n+1)/2);
        int actualSum=0;

        for (int i : nums) {
                actualSum+=i;
        }

        return expectedSum-actualSum;   
    }
}

Explanation

Sum of Integers Formula is n(n+1)/ 2

{1,2,3}->n is 3-> 3(3+1)/ 2-> expected sum: 6

{1,0,3}->n is 3-> actual sum: 4

missing integer : 6-4=2

Hashing O(n), O(n)

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;

        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < n; i++) {
            set.add(nums[i]);
        }

        for (int i = 0; i < n+1; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }

        return -1;
    }
}

Explanation

1. put all of integer into Hashset
2. if not contain the value that supposed contain, that is the value we looked for.

XOR Bit Manipulation O(n), O(1)

class Solution {
    public int missingNumber(int[] nums) {
        int xor = 0;
       int i = 0;

        for (int value:nums) {
         xor = xor ^ i ^ value;
            ++i;
        }

    return xor ^ i;
    }
}

Explanation

XOR symbol=Exclusive OR=carrot (^) symbol

1. 1 ^ 1 =0 , 0 ^ 0 =0 -> same number ^ same number = 0 -> n^n=0
2. a^(b^c) = (a^b)^c -> a^b = b^c
3. a^a^b^b=0
4. a^a^b^b^c=c
5. expected values^actual values=missing number

{1,2,3}->1^2^3

{1,0,3}->1^0^3

1^2^3^1^0^3

=1^1^0^3^3^2

=0^0^0^2

=2

missing integer : 2