Given a limited range array of size n having elements from 1 to n-1 contains a duplicate. Find the duplicate.
Example – A = [1,2,3,4,5,6,7,8,8] n = 9 ( 8 has a duplicate).
- Hashing – Keep track of all the numbers encountered while traversing. Space complexity O(n). Time complexity O(n).
- Sign – We can solve this problem in constant space also. Since the array contains all distinct elements except one and all elements lies in range 1 to n-1 , we can check for duplicate element by marking array elements as negative by using array index as a key. For each array element arr[i], we invert the sign of element present at index (arr[i]-1) and when we traverse the array again if we find an element positive, that arr[i] is our duplicate.
- In one traversal (above approach) – mark negative of element at (arr[i]-1) and if the element is already negative then return arr[i].(T.C O(n), S.C (1))
- XOR method – Take xor of all the elements in the array and then with integers from 1 to n-1. The left element will be the duplicate as elements xoring with itself returns 0 and the left element will be a duplicate lets say d, and 0^d = d. (T.C O(n), S.C (1))
- Difference – Find sum of the actual array elements and expected elements (from n*(n-1)/2) and subtract actual – expected to get the extra/duplicate element.