Given an array of n elements that contains numbers from 1 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 using only constant memory space, O(1).
Input: {1, 2, 3, 2, 1, 3, 4}
Output: 2 1 3
Solutions
Method 1: Marking elements (-)ve
The idea is to iterate the array from 0 to n-1 and mark the arr[i]th element as -ve, if arr[i]th element is -ve print arr[i].
The below code doesn't work if "0" is present in the array.
It will not work if the array contains more than 2 duplicates of an element. For example: {1, 2, 3, 1, 1, 3, 4} it will give output as : 1 1 3.
This more than 2 duplicates issue can be resolved by iterating the array twice. In the first iteration, mark the element -ve only if it is positive, and in the second iteration, print the index of -ve elements.
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).
Method 2: Adding "n" and using modulus "n"
This solution works for "0" as an element and also handles scenarios when there are more than two duplicates of an element present in the array.
The idea is to iterate the array from 0 to n-1 and add "n" to the element at the arr[i]th index.
If any element "e" occurs more than once, the "eth" index will have a value greater than or equal to 2 * n.
Iterate the array a second time and print the "index" of elements having a value greater than or equal to 2 * n.
In this solution, only one thing is left to be taken care of. As we are adding n to array elements, this will cause an "ArrayIndexOutOfBoundsException" while trying to get "arr[arr[i]]" because arr[i] is also acting as an index and the value will be out of the n-1 range. (n is added to the element at arr[i] for every occurance of "i").
To overcome this, the only change needed is to get "arr[i] % n" instead of "arr[i]" - so for an array of length n = 4, if element "3" is present twice and 2 is present at index 3, the element at index 3 will be converted to 2+4=6 and 2+4+4=10.
Now using "%", we can get 6%4 = 2 and 10%4 = 2 (no "ArrayIndexOutOfBoundsException").