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.
The idea that came to my mind first involved using a hash-table.
– Go over all the elements in the second array and add them to the hash table
– Go over all the elements in the first array and try to get it from the hash table. If it is not there, that’s the number.
The hash table solution has a complexity of O(n) but it uses a lot of space by creating a hash table with all the elements in the array.