Posts Missing number in array (geeksforgeeks - SDE Sheet)
Post
Cancel

Missing number in array (geeksforgeeks - SDE Sheet)

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.

geeksforgeeks

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

}
This post is licensed under CC BY 4.0 by the author.