We have array a[ ]= {1, 2, 3, 4, 5, 6, 7, 8, 4, 10};

And we need to find a number which is duplicate in O(n) and Space complexity O(1)

**Method 1 ) Sorting**

Sort it and u’ll get array = 1, 2, 3, 4, 4, 5, 6, 7, 8, 10 and find repeating element such that its index are different, but sorting takes O(nlogn)

**Method 2) Hashing.**

Keep Hashmap with <key, count> pair

Hashmap will contain

1,1

2,1

3,1

4,2

and return 4.

But it will take O(n) space Complexity

**Method 3) Changing Array**

Check if A [ abs(A[i]) ] is positive, then make it negative,

if its already negative then we found number.

( This trick will work only if all numbers are positive )

say array is 1, 2, 3, 4, 5, 6, 7, 8, 4, 10

so

while processing 1, w’ll make A[1] = -A[1], so 2 will become -2.

while processing 2, w’ll make A[2] = -A[2], so 3 will become -3.

while processing 3, w’ll make A[3] = -A[3], so 4 will become -4.

while processing 4, w’ll make A[4] = -A[4], so 5 will become -5.

while processing 5, w’ll make A[5] = -A[5], so 6 will become -6.

.

.

.

while processing 4, we checked that A[4] is already negative, So this is duplicate number.

-In order to get Original Array, we can make all sign as positive after wards

(Write/Append this code in ur code)

Working Code http://ideone.com/Y9eStG

#include <iostream>

using namespace std;

int main() {

int a[]= {1,2,3,4,5,6,7,8,4,10};

for(int i=0;i<sizeof(a)/sizeof(*a);i++){

if ( a[abs(a[i])]>0 ){

a[abs(a[i])]=-(a[abs(a[i])]);

}

else if (a[abs(a[i])]<0){

cout<<abs(a[i])<<endl;

}

}

for(int i=0;i<sizeof(a)/sizeof(*a);i++){

cout << a[i] <<endl;

}

return 0;

}

Duplicate

4

1 -2 -3 -4 -5 -6 -7 -8 -4 10