C Program to count total number of duplicate elements in an array

In C programming, managing and processing arrays is a common task. One such task is to count the total number of duplicate elements in an array. This article will guide you through writing a C program that counts the total number of duplicate elements in an array, explaining the logic and providing sample code.

Steps to Count Duplicate Elements

To count the total number of duplicate elements in an array, we can follow these steps:

1. Input the Array: Read the array elements from the user.
2. Identify Duplicate Elements: Check each element to determine if it is a duplicate.
3. Count Duplicates: Keep a count of the duplicate elements.

We'll discuss two methods to achieve this:

1. Using Nested Loops: This method involves comparing each element with every other element in the array.
2. Using a Frequency Array: This method uses an auxiliary array to keep track of the frequency of each element.

Method 1: Using Nested Loops

#include <stdio.h>

int main() {
    int size;
    printf("Enter the size of the array: ");
    scanf("%d", &size);

    int arr[size];
    printf("Enter %d elements- \n", size);
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }

    int duplicateCount = 0;

    for (int i = 0; i < size; i++) {
        int isDuplicate = 0;
        for (int j = 0; j < i; j++) {
            if (arr[i] == arr[j]) {
                isDuplicate = 1;
                break;
            }
        }
        if (isDuplicate) {
            duplicateCount++;
        }
    }

    printf("Total number of duplicate elements: %d", duplicateCount);

    return 0;
}

Explanation:

1. Input the Array: The user inputs the size of the array and the elements.
2. Identify Duplicate Elements: The program uses two nested loops. The outer loop iterates through each element, and the inner loop checks if the current element is equal to any previous element.
3. Count Duplicates: When a duplicate is found, the duplicateCount is incremented.

Advantages:

• Simple and easy to understand.
• No additional memory required apart from the input array.

Disadvantages:

• Time complexity is O(n^2), making it inefficient for large arrays.

Method 2: Using a Frequency Array

#include <stdio.h>

int main() {
    int size;
    printf("Enter the size of the array: ");
    scanf("%d", &size);

    int arr[size];
    printf("Enter %d elements -\n", size);
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }

    int maxVal = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }

    int freq[maxVal + 1];
    for (int i = 0; i <= maxVal; i++) {
        freq[i] = 0;
    }

    for (int i = 0; i < size; i++) {
        freq[arr[i]]++;
    }

    int duplicateCount = 0;
    for (int i = 0; i <= maxVal; i++) {
        if (freq[i] > 1) {
            duplicateCount += freq[i] - 1;
        }
    }

    printf("Total number of duplicate elements: %d", duplicateCount);

    return 0;
}

Explanation:

1. Input the Array: The user inputs the size of the array and the elements.
2. Find Maximum Value: The program finds the maximum value in the array to determine the size of the frequency array.
3. Frequency Array: The program initializes a frequency array to zero. It then iterates through the input array, incrementing the frequency of each element.
4. Count Duplicates: The program iterates through the frequency array, and for each element with a frequency greater than one, it adds the count minus one to duplicateCount.

Advantages:

• More efficient with a time complexity of O(n).
• Suitable for larger arrays compared to the nested loop method.

Disadvantages:

• Requires additional memory for the frequency array.
• Assumes a known range of possible values in the array.

Output

Enter the size of the array: 10
Enter 10 elements-
1
2
1
2
3
4
5
6
7
8
Total number of duplicate elements: 2