In this blog post, we learn how to write a C program to find a duplicate in an array? So here we will write the C program to find a duplicate in a given array. We will also see how to display the duplicate number of a given integer array using C programming.
Example,
Input: [1, 2, 2, 3,4] Output: 2 Input: [2,3, 4, 1, 4, 1,7] Output: 4 or 1
So let’s see the logic to find all the duplicate elements in the given array. Suppose arr is an integer array of size N (arr[N] ), the task is to write the C program to find a duplicate element in an array.
Solution 1: Brute Force
It is the simplest solution to print the duplicate element in a given array. In which you need to use nested loops. The outer loop picks elements one by one and counts the number of occurrences of the picked element in the inner loop. The time complexity of this solution is O(n²) and space complexity O(1).
Note: Mentioned C program works fine if the element appears only twice. If the elements appear more than twice then it would not work.
#include<stdio.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
//only work if element appear twice or once
void findDuplicateElement(int arr[], const int size)
{
int i, j;
printf("Repeating elements are ");
for(i = 0; i < size; i++)
{
for(j = i+1; j < size; j++)
{
if(arr[i] == arr[j])
{
printf(" %d ", arr[i]);
}
}
}
}
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 1};
const int N = ARRAY_SIZE(arr);
findDuplicateElement(arr, N);
return 0;
}
Output:
As I have mentioned in notes that if the array elements appear more than twice, then the above program will not work. But with some small modification, it will work fine with an array that contains the same element multiple times.
Here I am explaining a simple solution in which you just need to introduce another temporary array that is going to store the elements which are repeated in the array. You need to start filling this array from the 0th index.
It will fill when you find a newly repeated element. This can easily be done by iterating through this new array and checking if the currently encountered repeated element is already present or not. If it is not present there, then insert it into the new array.
for(k = 0; k < tmpArrIndex; k++)
{
if(tmpArr[k] == arr[j])
{
//It is not a newly repeated element
flag = 1;
}
}
if(flag != 1)
{
//newly repeated element
tmpArr[tmpArrIndex++] = arr[j];
}
Let’s see an example code for better understanding.,
#include<stdio.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
void findDuplicateElement(int arr[], const int size)
{
int i, j,k;
int tmpArr[size],tmpArrIndex = 0;
printf("Repeating elements are ");
for(i = 0; i < size; i++)
{
int flag = 0;
for(j = i+1; j < size; j++)
{
if((i != j) && (arr[i] == arr[j]))
{
for(k = 0; k < tmpArrIndex; k++)
{
if(tmpArr[k] == arr[j])
{
//It is not a newly repeated element
flag = 1;
}
}
if(flag != 1)
{
//newly repeated element
tmpArr[tmpArrIndex++] = arr[j];
}
}
}
}
//print duplicate element
for(i = 0; i < tmpArrIndex; i++)
{
printf("%d ",tmpArr[i]);
}
}
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 1,4,4,4,4,1,2,34,4,4,4,4,4,4};
const int N = ARRAY_SIZE(arr);
findDuplicateElement(arr, N);
return 0;
}
Output:
If you want to learn more about the c language, here 10 Free days (up to 200 minutes) C video course for you.
Your free trial is waiting
Solution 2: Finding duplicates in O(n) time and O(1) space
It is an optimized way to find the duplicates in a given array. But this solution has the limitation that the array elements must be between 0 to n-1, where n is the size of the array.
//Input array
int arr[] = {4, 2, 4, 5,4,1,2,3}; //correct input
int arr[] = {4, 2, 44, 3,4}; //Wrong input
int arr[] = {-4, 2, -4, 3,4}; //Wrong input
Let’s see the code for a better understanding,
#include<stdio.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
void findDuplicateElement(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
{
if (arr[abs(arr[i])] >= 0)
{
arr[abs(arr[i])] *= -1;
}
else
{
printf("%d ",arr[i]);
}
}
}
int main()
{
int arr[] = {1,4,0,4,3,2,1,0,5};
const int N = ARRAY_SIZE(arr);
findDuplicateElement(arr, N);
return 0;
}
Output:
Solution 3:
It is also an optimized way to find the duplicates in a given array. But this solution has the limitation that the array elements must be between 0 to n-1, where n is the size of the array.
#include<stdio.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
void findDuplicateElement(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
{
while (arr[arr[i]] != arr[i])
{
int tmp = arr[i];
arr[i] = arr[tmp];
arr[tmp] = tmp;
}
}
for (i = 0; i < n; ++i)
{
if (arr[i] != i && arr[arr[i]] == arr[i])
{
printf("%d ",arr[i]);
arr[arr[i]] = i;
}
}
}
int main()
{
int arr[] = {1,4,0,4,3,2,1,0,5};
const int N = ARRAY_SIZE(arr);
findDuplicateElement(arr, N);
return 0;
}
Output:
1 0 4
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- C program to find sum of all sub-array of a given array.
- C program to segregate even and odd numbers
- Find an element in array such that sum of left array is equal to sum of right array.
- C Program to find the count of even and odd elements in the array.
- Write C program to find the sum of array elements.
- Find the sum of array elements using recursion
- C Program to reverse the elements of an array
- C Program to find the maximum and minimum element in the array
- Calculate size of an array in without using sizeof in C
- How to create a dynamic array in C?
- How to access 2d array in C?
- Dangling, Void, Null and Wild Pointers
- Function pointer in c, a detailed guide
- How to use the structure of function pointer in c language?
- Memory Layout in C.
- 100 C interview Questions
- File handling in C.
One comment