Programming Interview Questions 4: Find Missing Element | Arden DertatArden Dertat
Using XOR:
nitialize a variable to 0, then XOR every element in the first and second arrays with that variable. In the end, the value of the variable is the result, missing element in array2 .
O(N) time and space.
We can use a hashtable and store the number of times each element appears in the second array. Then for each element in the first array we decrement its counter. Once hit an element with zero count that’s the missing element.
Read full article from Programming Interview Questions 4: Find Missing Element | Arden DertatArden Dertat
There is an array of non-negative integers. A second array is formed by shuffling the elements of the first array and deleting a random element. Given these two arrays, find which element is missing in the second array. Here is an example input, the first array is shuffled and the number 5 is removed to construct the second array.
nitialize a variable to 0, then XOR every element in the first and second arrays with that variable. In the end, the value of the variable is the result, missing element in array2 .
O(N) time and space.
We can use a hashtable and store the number of times each element appears in the second array. Then for each element in the first array we decrement its counter. Once hit an element with zero count that’s the missing element.
Read full article from Programming Interview Questions 4: Find Missing Element | Arden DertatArden Dertat
