#### Arrays & Strings

Problem
Find the duplicate elements in an array of size n where each element is in the range 0 to n-1.

Solution
Approach 1 :: Compare each element of the array with all other elements (using two loops) [ O(n2) solution ( not an efficient one) ]
Approach 2 :: Maintain a hash table. Set the hash value to 1 if we encounter the element for the first time. If we see it second time ( we check it by looking at the hash value ), print it [ efficient in terms of time O(n) but additional space is required ]
Approach 3 :: We will exploit the constraintevery element is in the range 0 to n-1“.
Suppose we see an element 4 in the array. We will make arr[4] negative.
So while traversing the array, if we see a negative value, we will print the index of that value.
Considering our example, we will find arr[4] negative and so we will print 4.

```#include<iostream>
#include<cmath>
using namespace std;

// find all the duplicate elements in an array of size
// 'n' where all elements are in the range 0 to n-1
// If an element 'k' is present in an array, we will
// make the value at index 'k' negative
// i.e if k = 4 then arr[k] = -arr[k]
void findDuplicates(int arr[],int size) {
int i;
int k;
for (i=0;i<size;i++) {
k = abs(arr[i]);
if (arr[k] >= 0) {
// k was not seen previously
// mark k as seen
arr[k] = -arr[k];
}
else {
// arr[k] is negative
// this implies 'k' was seen previously
cout<<k<<" ";
}
}
}

// main
int main() {
int arr[] = {3,5,1,6,5,7,3,6};
int size = sizeof(arr)/sizeof(arr[0]);
findDuplicates(arr,size);
cout<<endl;
return 0;
}```