PROBLEM DESCRIPTION
Given an array of size N-1 such that it only contains distinct integers in the range of 1 to N. Find the missing element.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
int missingNumber(int array[], int n) {
// Initialize x as the size of the array (n)
int x = n;
for(int i=0; i<array.length; i++){
// We want x to be:
// 1) XOR of all values from 1,2,3,4...N
// 2) XOR of all values from a[0],a[1]...a[n-1]
// We know that x ^ x = 0
// So, if we XOR 1) and 2) from above, only the missing element will be left behind
x ^= array[i];
x ^= i+1;
}
// After the loop, x will contain the missing element
return x;
}
}