Given an array, find all the repeated elements in C language.

Problem Description:

Given a positive integer array, find all the elements that have been repeated and display them.

Example:

Input:

{1, 3, 2, 7, 5, 1, 3}

Output:

1, 3

Solution:

The solution is very simple.

We traverse through the array and make the element in that index as negative. This means the element is unique at that time.

We can achieve that from the below formula:

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

Here abs( ) will return +ve value of the element.

Then if the same element repeats we check if the element is –ve. If –ve then we take it as repeated element.

Below is how the algorithm work:

Input: {1, 5, 1, 3}

pass 0:
	i = 0
	arr[ arr [0] ] is -ve ? NO 
	arr[ arr[0] ] = - arr[ arr[0] ];
	arr[ 1 ] = -arr [ 1 ];
	arr[ 1 ] = -5

pass 1:
	i = 1
	arr[ arr[1] ] is -ve ? NO
	arr[ arr[1] ] = - arr[ arr[1] ];
	arr [ 5 ] = -arr [5]
	arr [ 5 ] = -5

pass 2:
	i = 2
	arr[ arr[2] ] is -ve 
	
	Hence this element is repeated.

Solution in C

#include <stdio.h>
#include <stdlib.h>
 
void checkduplicate(int arr[], int length)
{
  int i;
  printf("The repeating elements are: \n");
  for (i = 0; i < length; i++)
  {
    if (arr[abs(arr[i])] >= 0)
    {
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    }
    else
      printf(" %d ", abs(arr[i]));
  }
  printf("\n");
}
 
int main()
{
  int arr[] = {1, 3, 2, 7, 5, 1, 3};
  int length = 7;
  checkduplicate(arr, length);
  return 0;
}

Output:

The repeating elements are:
 1  3