C program to find a duplicate element in an array

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:

find duplicate element in c

 

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:

Repeated element multiple times in array in c

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:

Finding duplicates in O(n) time and O(1) space

 

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: