#### 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(n ^{2})** 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

**constraint**“

**every 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; }