Find missing number

In an Unsorted Array size N - 1 of 1 to N, find the missing number in O(n) time

Solution 1: HashMap

Average case: O(N)

Worst Case: O(N^2)

Solution 2: Boolean Array

input: 7 2 4 1 5 3

boolArr: 1? 2? 3? 4? 5? 6? 7?

Total num = input.length + 1 = 7

Boolean[] boolArr = new Boolean[input + 1];
Arrays.fill(array, Boolean.FALSE);

for (int cur: input){
    boolArr[cur - 1] = true; //int 7 -> boolArr[6] = true
}
for (int i = 0; i < boolArr.length; i++){
    if (boolArr[i] == false) System.out.println(i + 1);
}

Time Comp: O(traverse input + traverse boolArr) = O(2N) = (N)

Solution 3: Subtract

int sum = 0;
for (int i = 1; i <= input.length + 1; i++){
    sum += i;
}

int cursum = 0;
for (int i: input){
    cursum += i
}

return sum - cursum;

Time Comp: O(traverse input + add 1->N) = O(N + N) = O(2N) = O(N)

Solution 4: XOR

  public int missing(int[] array) {

    if (array.length == 0) return 1; 

    //XOR method 
    int x1 = array[0];
    int x2 = 1;
    int n = array.length;

    //XOR input array 1 -> n
    for ( int i = 1; i < n; i++){
      x1 = x1 ^ array[i];
    }

    //XOR ideal array 1 -> n + 1
    for (int i = 2; i <= n + 1; i++){
      x2 = x2 ^ i;
    }

    return (x1 ^ x2);
  }

Time Comp: O(One traversal + N XOR in x2) = O(2N) = O(N)

Space Comp: O(1)