Find duplicates in O(n) time and O(1) extra space | GeeksforGeeks

Find duplicates in O(n) time and O(1) extra space | GeeksforGeeks
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.

When asked no extra space, consider modify the origin data in place, and use index to indicate element.

This problem is an extended version of following problem.

Find the two repeating elements in a given array

traverse the list for i= 0 to n-1 elements
{
  check for sign of A[abs(A[i])] ;
  if positive then
     make it negative by   A[abs(A[i])]=-A[abs(A[i])];
  else  // i.e., A[abs(A[i])] is negative
     this   element (ith element of list) is a repetition
}

void printRepeating(int arr[], int size)

{

  int i;

  printf("The repeating elements are: \n");

  for (i = 0; i < size; i++)

  {

    if (arr[abs(arr[i])] >= 0)

      arr[abs(arr[i])] = -arr[abs(arr[i])];

    else

      printf(" %d ", abs(arr[i]));

  }

}
Note: The above program doesn’t handle 0 case (If 0 is present in array). The program can be easily modified to handle that also. It is not handled to keep the code simple.

X. http://tristan-xi.org/?p=321
Find duplicates in O(n) time and O(1) extra space | GeeksforGeeks
Find duplicates in O(n) time and O(1) extra space | GeeksforGeeks
Read full article from Find duplicates in O(n) time and O(1) extra space | GeeksforGeeks