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