CareerCup

Check whether A[i] is already put into into A[A[i]].
If yes -> duplicate.
If no, swap(A[i], A[A[i]])

take the xor for 1 to n-1.....lets say x=(1^2^....^n-1)
now xor x with all elements from 1 to n in the array...
the result is the required no...

void main()
{
int a[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,13};

int x =a[0];

for (int i=1;i<17;i++)
x^=(i^a[i]);

cout<<x<<endl;

char c =getchar();
while( c!=32) c=getchar();

}

Try to construct a binary tree from N numbers, on course you can find the duplicate.

One of the best algorithms to solve the above problem statement is to use the concept of bit manipulation, we will first xor all the numbers from 1 to n - 1 and we will then xor all the array elements and store them in a separate variable and at the end, we will xor both of them together and finally we will get the duplicate element in the array.

Implementation:

int findrepeating(int arr[], int n){
	int xor_numbers = 1;
	int xor_array = arr[0];
	for(int i = 2; i <= n - 1; i++)
		xor_numbers = xor_numbers ^ i;
	for(int i = 1; i < n; i++)
		xor_array = xor_array ^ arr[i];
	return xor_numbers ^ xor_array;
}