Find duplicate in an array in O(n) and by using O(1) extra space in C++

Suppose we have a list of numbers from 0 to n-1. A number can be repeated as many as a possible number of times. We have to find the repeating numbers without taking any extra space. If the value of n = 7, and list is like [5, 2, 3, 5, 1, 6, 2, 3, 4, 5]. The answer will be 5, 2, 3.

To solve this, we have to follow these steps −

• for each element e in the list, do the following steps −
  • sign := A[absolute value of e]
  • if the sign is positive, then make it negative
  • Otherwise, it is a repetition.

Example

 Live Demo

#include<iostream> #include<cmath> using namespace std; void findDuplicates(int arr[], int size) {    for (int i = 0; i < size; i++) {       if (arr[abs(arr[i])] >= 0)          arr[abs(arr[i])] *= -1;       else          cout << abs(arr[i]) << " ";    } } int main() {    int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1};    int n = sizeof(arr)/sizeof(arr[0]);    findDuplicates(arr, n); }

Output

5 2 3 1