Find duplicate elements in array in C
What is an array?
An array is a basic computer data structure that enables you to keep a group of identically sized elements in a single block of memory. An array's index or location inside the array is used to access each element. Because they offer effective and organized ways to handle and manipulate several types of data, arrays are often employed.
What is a duplicate element?
A quantity that occurs more than once in a data set is a duplicate element. Duplicate elements are situations where the same value appears more than once in arrays or other data structures. These duplicates can appear in various programming settings and be of any data type, including integers, characters, strings, and more sophisticated objects.
Program to find duplicate elements in array
#include <stdio.h>
void findDuplicates(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (arr[i] == arr[j]) {
printf("Duplicate element: %d\n", arr[i]);
}
}
}
}
int main() {
int arr[] = {2, 4, 6, 8, 2, 9, 6};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Array elements:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
printf("Duplicate elements in the array:\n");
findDuplicates(arr, size);
return 0;
}
Output:
![Find duplicate elements in array in C](https://static.tutorialandexample.com/c/find-duplicate-elements-in-array-in-c1.png)
Different methods used:
- Loops Nested (Brute Force):
The simplest method compares every component with all succeeding items using stacked loops. If an exact match is discovered, it is seen as a duplicate.
Program:
#include <stdio.h>
void findDuplicates(int arr[], int size) {
printf("Duplicate elements in the array:\n");
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (arr[i] == arr[j]) {
printf("%d\n", arr[i]);
}
}
}
}
int main() {
int arr[] = {2, 4, 6, 8, 2, 9, 6};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Array elements:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
findDuplicates(arr, size);
return 0;
}
Output:
![Find duplicate elements in array in C](https://static.tutorialandexample.com/c/find-duplicate-elements-in-array-in-c2.png)
- Hashing:
To keep updated on the components you've come across, utilize a hash table. A duplicate element is one that already exists in the hash table.
Program
#include <stdio.h>
void findDuplicates(int arr[], int size) {
const int MAX_VALUE = 1000; // Assuming a maximum value for the elements
int hashTable[MAX_VALUE + 1] = {0};
printf("Duplicate elements in the array:\n");
for (int i = 0; i < size; i++) {
if (hashTable[arr[i]] == 1) {
printf("%d\n", arr[i]);
} else {
hashTable[arr[i]] = 1;
}
}
}
int main() {
int arr[] = {2, 4, 6, 8, 2, 9, 6};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Array elements:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
findDuplicates(arr, size);
return 0;
}
Output:
![Find duplicate elements in array in C](https://static.tutorialandexample.com/c/find-duplicate-elements-in-array-in-c3.png)
- Sorting:
Duplicate elements will be next if you arrange the array first. The sorted array may then be quickly browsed through to look for duplicates.
Program:
#include <stdio.h>
#include <stdlib.h>
// Comparison function for qsort
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
void findDuplicates(int arr[], int size) {
qsort(arr, size, sizeof(int), compare);
printf("Duplicate elements in the array:\n");
for (int i = 1; i < size; i++) {
if (arr[i] == arr[i - 1]) {
printf("%d\n", arr[i]);
}
}
}
int main() {
int arr[] = {2, 4, 6, 8, 2, 9, 6};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Array elements:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
findDuplicates(arr, size);
return 0;
}
Output:
![Find duplicate elements in array in C](https://static.tutorialandexample.com/c/find-duplicate-elements-in-array-in-c4.png)
- Bit manipulation for a constrained set of elements:
If the elements' range is constrained, bitwise operations can effectively find duplicates.
Program:
#include <stdio.h>
#include <stdbool.h>
void findDuplicates(int arr[], int size) {
int bitSet = 0;
bool foundDuplicates = false;
printf("Duplicate elements in the array:\n");
for (int i = 0; i < size; i++) {
int bit = 1 << arr[i];
if (bitSet & bit) {
printf("%d\n", arr[i]);
foundDuplicates = true;
} else {
bitSet |= bit;
}
}
if (!foundDuplicates) {
printf("No duplicates found.\n");
}
}
int main() {
int arr[] = {2, 4, 6, 8, 2, 9, 6};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Array elements:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
findDuplicates(arr, size);
return 0;
}
Output:
![Find duplicate elements in array in C](https://static.tutorialandexample.com/c/find-duplicate-elements-in-array-in-c5.png)
Time complexity:
1.Loops Nested (Brute Force):
In this method, you evaluate each element with each successive element using two stacked loops. The worst-case temporal complexity, wherein n is the array's element count, is O(n2).
2.Hashing:
When using hashing, the array is iterated through once to add entries to the hashing table and once again to look for duplicates. The worst-case scenario for both the temporal complexity of checking for duplicates and entering entries into a hash table is O(n). As a result, O(n) is the general time complexity.
3.Sorting:
The array must first be sorted as part of the sorting technique, which often entails utilising quicksort, mergesort, or another fast-sorting algorithm. You repeat once across the sorted array after sorting to find duplicates. The sorting phase dominates the overall time complexity, O(n log n), because the duplicate-checking portion requires O(n) time.
4.manipulating bits
The bit manipulation method does a single iteration of the array and uses bitwise operations to keep track of encountered elements. The array's size, n, determines the linear time complexities of this method, which is O(n).
The hashing and data manipulation techniques have the most effective time complexity of O(n). Although still rather effective, the sorting strategy has a greater temporal complexity because of the sorting phase. The nested loop method has quadratic temporal complexity, making it the least efficient, especially for bigger arrays.