## Finding duplicates in O(n)

Input: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.

Goal : To find these repeating numbers in O(n) and using only constant memory space.

#include <iostream> using namespace std; void duplicates(int a[], int n) { for (int i = 0; i < n; i++) { while(a[a[i]]!=a[i]) swap(a[a[i]],a[i]); } for (int i = 0; i < n; i++) if (a[i] != i) cout<<a[i]<<" "; } int main() { int x[] = {1, 2, 3, 1, 3, 0, 6}; int n = sizeof x / sizeof x[0]; duplicates(x, n); return 0; }

Advertisements