Given an array of n elements that contains numbers from 0 to n-1, with any of these numbers appearing any number of times in any order (non-sorted).
Find these repeating numbers in O(n) time and O(n) memory space.
Return -1 if there is no duplicate.
Input: {0, 3, 1, 2}
Output: -1
Input: {2, 3, 1, 0, 3, 2, 3, 0}
Output: 3, 2, 0
Solutions
Method 1: Using an extra array of length "n"
Traverse the given array and keep track of the count of all elements in the array using a temporary array tmp[] of size n.
When you see an element whose count is already "1" print it. This specific "tmp[arr[i]] == 1" check will handle scenarios where an element occurs more than 2 times.
This method uses the range given in the question to restrict the size of tmp[].
Complexity
The time complexity of this solution is O(n) and space complexity is O(n).