**Tags**

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5

The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

**Solution** **1**: basic solution would be traversal the array twice. it would take O(n^2) time and O(1) space.

**Solution 2**: use hash table or another hash set, the algorithm would be O(n) space complexity and O(n) time complexity.

**Solution 3:** a trick way to do this in O(n) time complexity and O(1) space complexity would be using the given condition that all element is from range 1 to n. we can use each element value as index, change element with that index to negative value. see here for more detailed information.

e.g

Traverse the array. Do following for every index i of A[]. { check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // i.e., A[abs(A[i])] is negative this element (ith element of list) is a repetition }

Example: A[] = {1, 1, 2, 3, 2} i=0; Check sign of A[abs(A[0])] which is A[1]. A[1] is positive, so make it negative. Array now becomes {1, -1, 2, 3, 2} i=1; Check sign of A[abs(A[1])] which is A[1]. A[1] is negative, so A[1] is a repetition. i=2; Check sign of A[abs(A[2])] which is A[2]. A[2] is positive, so make it negative. ' Array now becomes {1, -1, -2, 3, 2} i=3; Check sign of A[abs(A[3])] which is A[3]. A[3] is positive, so make it negative. Array now becomes {1, -1, -2, -3, 2} i=4; Check sign of A[abs(A[4])] which is A[2]. A[2] is negative, so A[4] is a repetition.