The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

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<<" ";
}
}
}
// mainint 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;
}

#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<<" ";
}
}
}
// mainint 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;
}