C Program to Remove Duplicate Elements from an Array

What is Array?

An array is a collection of similar data elements stored in a contiguous memory location.

Example: arr[5] = {2,7,1,23,5}

Array example with value and index.

Example:
Input Array: 1,2,4,5,4,2,7,5

Output: Resultant Array after removing duplicates: 1,2,4,5,7

Problem Description

Write a C Program to remove duplicate elements from an Array.

Problem Solution

1. Take size of the array n as input from user.
2. Initialize an array arr of size n.
3. Enter the elements into the array.
4. Run two for loops and check for unique elements.
5. Store all the unique elements in another array temp.
6. Print all the elements inside the array temp.
7. Exit.

advertisement
advertisement

There are several ways to remove duplicate elements from an array in C language. Let’s take a detailed look at all the approaches to remove duplicate elements from an array.

Method 1: (Using Nested For Loop)

In this approach, we remove duplicate elements from array using nested for loop.

Program/Source Code

Here is the source code of the C program to remove duplicate elements from array using nested for loop. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to remove duplicates from array using nested for loop
  3.  */
  4.  
  5. #include <stdio.h>
  6. int main()
  7. {
  8.     int n, count = 0;
  9.     printf("Enter number of elements in the array: ");
  10.     scanf("%d", &n);
  11.     int arr[n], temp[n];
  12.     if(n==0)
  13.     {
  14.         printf("No element inside the array.");
  15.         exit(0);
  16.     }
  17.     printf("Enter elements in the array: ");
  18.     for (int i = 0; i < n; i++)
  19.     {
  20.         scanf("%d", &arr[i]);
  21.     }
  22.  
  23.     printf("\nArray Before Removing Duplicates: ");
  24.     for (int i = 0; i < n; i++)
  25.         printf("%d ", arr[i]);
  26.  
  27.     // To store unique elements in temp after removing the duplicate elements
  28.     for (int i = 0; i < n; i++)
  29.     {
  30.         int j;
  31.         for (j = 0; j < count; j++)
  32.         {
  33.           if (arr[i] == temp[j])
  34.             break;
  35.         }
  36.         if (j == count)
  37.         {
  38.           temp[count] = arr[i];
  39.           count++;
  40.         }
  41.     }
  42.  
  43.     printf("\nArray After  Removing Duplicates: ");
  44.     for (int i = 0; i < count; i++)
  45.         printf("%d ", temp[i]);
  46.  
  47.     return 0;
  48. }
Program Explanation

1. Take the number, n as input from the user.
2. Declare an array of size n.
3. Enter n elements into the array.
4. If n = 0 means there is no element in the array. Print there is no element in the array and exit.
5. Print the array before removing the duplicates.
6. Run a nested loop first one is to copy the element from the array to temp array.
7. If that element is existing already in temp variable, then we will break the inner loop and continue executing for remaining elements the same process.
8. After coming out of the loop all the unique elements have been stored in the temp array.
9. Print the elements in the temp array, this is the array after removing the duplicates from the array.
10. Exit.

Example: (Step by Step Procedure to Remove Duplicates from an Array)
Let the array be of size 6 and array elements be 3, 2, 3, 4, 2, 4 i.e.,
arr =

3 2 3 4 2 4

Initialize another array temp of size 6 to store all the unique elements and a count variable to keep count of elements in temp array.

Step 1:
Store the 1st element of arr to temp array and make count=1.

advertisement

temp =

3

Run the for loop from i = 1 to n and in each step check if the element is already present in the temp array. If element is already present in the temp array skip to the next element and if element is not present in the temp array insert the element in the temp array and increase the value of count by 1.

Step 2:
For i=1, arr[1] = 2. Run another for loop from j=0 to count and check if arr[i] element is present or not. Since count = 1, inner for loop will run only once, and element in the temp[0] = 3. Since, temp[0] not equal to arr[1] we will insert 2 in the temp array and count = 2.

temp =

3 2

Step 3:
For i=2, arr[2] = 3. Run another for loop from j=0 to count=2 and check if arr[i] element is present or not. temp[0] = 3, which is equal to arr[2] i.e., element is already present in temp array so we will break the inner for loop and increment the value of i by 1 in the outer loop, i.e. i=3.

advertisement

Step 4:
For i=3, arr[3] = 4. Run another for loop from j=0 to count=2 and check if arr[i] element is present or not. Inside temp array we have 3 and 2 which is not equal to 4 so we will insert 4 in the temp array and increment count by 1 i.e., count = 3.

temp =

3 2 4

Step 5:
For i=4, arr[4] = 2. Run inner for loop from j=0 to count=3 and check if arr[i] element is present or not. temp[1] = 2, which is equal to arr[4] i.e., element is already present in temp array so we will break the inner for loop and increment the value of i by 1 in the outer loop, i.e. i=5.

Step 6:
For i=5, arr[5] = 4. Run another for loop from j=0 to count=3 and check if arr[i] element is present or not. temp[2] = 4, which is equal to arr[5] i.e., element is already present in temp array so we will break the inner for loop and increment the value of i by 1 in the outer loop, i.e. i=6.

Step 7:
Now, i=6 i.e., i is not less than n, therefore exit the outer for loop as entire array has been traversed. Now, run a for loop from j=0 to count and print all the elements in the temp array. These are the elements that is there in the array after removing all the duplicates.
Therefore, elements in the array after removing the duplicates are: 3, 2, 4.

Time Complexity: O(n2)
The above program for removing duplicates from an array has a time complexity of O(n^2) as there is a nested for loop which runs for n number of times.

Space Complexity: O(n)
In the above program, space complexity is O(n) as arrays arr[] and temp[] of size n has been initialized to store elements.

Runtime Test Cases

Testcase 1: In this case, the array has “8” elements, and the array elements are “9, 3, 6, 9, 5, 4, 0, and 5”.

Enter number of elements in the array: 8
Enter elements in the array: 9 3 6 9 5 4 0 5
 
Array Before Removing Duplicates: 9 3 6 9 5 4 0 5
Array After Removing Duplicates: 9 3 6 5 4 0

Testcase 2: In this case, the array has “5” elements, and the array elements are “3, 2, 3, 3, and 2”.

Enter number of elements in the array: 5
Enter elements in the array: 3 2 3 3 2
 
Array Before Removing Duplicates: 3 2 3 3 2
Array After Removing Duplicates: 3 2

Method 2: (Using Sort Function with Extra Space)

In this approach, we remove duplicate elements from array using sort function with extra space.

Program/Source Code

Here is the source code of the C program to remove duplicate elements from array using sort function with extra space. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  2.  * C Program to remove duplicates from array using sort function with extra space
  3.  */
  4.  
  5. #include<stdio.h>
  6. #include<stdlib.h>
  7.  
  8. //function cmpfunc to compare two numbers
  9. int cmpfunc(const void *a, const void *b)
  10. {
  11.     return(*(int*)a - *(int*)b);
  12. }
  13.  
  14. //main function
  15. int main()
  16. {
  17.     int n;
  18.     printf("Enter number of elements in the array: ");
  19.     scanf("%d",&n);
  20.     int arr[n];
  21.  
  22.     printf("Enter elements in the array: ");
  23.     for(int i=0;i<n;i++)
  24.         scanf("%d",&arr[i]);
  25.  
  26.     //if array is empty
  27.     if(n==0)
  28.     {
  29.         printf("No element inside the array.");
  30.         exit(0);
  31.     }
  32.  
  33.     printf("\nArray Before Removing Duplicates: ");
  34.     for (int i = 0; i < n; i++)
  35.         printf("%d ", arr[i]);
  36.  
  37.     //inbuilt function qsort to sort the array
  38.     qsort(arr,n,sizeof(int),cmpfunc);
  39.  
  40.     //temporary array to store only unique elements
  41.     int temp[n];
  42.     int i = 0, j = 0;
  43.     temp[j++] = arr[i++];
  44.  
  45.     //loop to remove duplicate elements and store
  46.     //unique elements in the array temp
  47.     for( ; i<n; i++)
  48.     {
  49.         if(arr[i] != arr[i-1])
  50.         {
  51.             temp[j++] = arr[i];
  52.         }
  53.     }
  54.  
  55.     //print the array after removing all the duplicate elements
  56.     printf("\nArray After Removing Duplicates: ");
  57.     for(i=0;i<j;i++)
  58.         printf("%d ",temp[i]);
  59.  
  60.     return 0;
  61. }
Program Explanation

1. Take the number, n as input from the user.
2. Declare an array of size n.
3. Enter n elements into the array.
4. If n = 0 means there is no element in the array. Print there is no element in the array and exit.
5. Print the array elements before removing the duplicates.
6. Sort the array using the function qsort().
7. The values that needs to be passed on the function qsort() are: arr, n, sizeof(int) and call to a function cmpfunc.
8. The function cmpfunc is used to compare two values at a time in an array.
9. After sorting the array initialize another array temp of size n.
10. Run a for loop till n and in each iteration check if arr[i] is equal to arr[i-1] or not.
11. If arr[i] is not equal to arr[i-1], enter the element at arr[i] to the array temp.
12. Repeat this step till i=n.
13. Now, the array temp contains all the unique values in a sorted order.
14. print all the elements present inside the array temp.
15. Exit.

Time Complexity: O(n log(n))
The above program for removing duplicates from an array has a time complexity of O(n log(n)) as the time complexity of qsort function i.e., quicksort is O(n log(n)).

Space Complexity: O(n)
In the above program, space complexity is O(n) as arrays arr[] and temp[] of size n has been initialized to store elements.

Runtime Test Cases

Testcase 1: In this case, the array has “8” elements, and the array elements are “9, 3, 6, 9, 5, 4, 0, and 5”.

Enter number of elements in the array: 8
Enter elements in the array: 9 3 6 9 5 4 0 5
 
Array Before Removing Duplicates: 9 3 6 9 5 4 0 5
Array After Removing Duplicates: 0 3 4 5 6 9

Testcase 2: In this case, the array has “5” elements, and the array elements are “3, 2, 3, 3, and 2”.

Enter number of elements in the array: 5
Enter elements in the array: 3 2 3 3 2
 
Array Before Removing Duplicates: 3 2 3 3 2
Array After Removing Duplicates: 2 3

Method 3: (Using Sort Function without Extra Space)

In this approach, we remove duplicate elements from array using sort function without extra space i.e., we will not use extra temp[], array to store the values. We will remove duplicates from the array arr[] itself without using any extra array.

Program/Source Code

Here is the source code of the C program to remove duplicate elements from array using sort function without extra space. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  2.  * C Program to remove duplicates from array using sort function without extra space
  3.  */
  4.  
  5. #include<stdio.h>
  6. #include<stdlib.h>
  7.  
  8. //function cmpfunc to compare two numbers
  9. int cmpfunc(const void *a, const void *b)
  10. {
  11.     return(*(int*)a - *(int*)b);
  12. }
  13.  
  14. //main function
  15. int main()
  16. {
  17.     int n;
  18.     printf("Enter number of elements in the array: ");
  19.     scanf("%d",&n);
  20.     int arr[n];
  21.  
  22.     printf("Enter elements in the array: ");
  23.     for(int i=0;i<n;i++)
  24.         scanf("%d",&arr[i]);
  25.  
  26.     //if array is empty
  27.     if(n==0)
  28.     {
  29.         printf("No element inside the array.");
  30.         exit(0);
  31.     }
  32.  
  33.     printf("\nArray Before Removing Duplicates: ");
  34.     for (int i = 0; i < n; i++)
  35.         printf("%d ", arr[i]);
  36.  
  37.     //inbuilt function qsort to sort the array
  38.     qsort(arr,n,sizeof(int),cmpfunc);
  39.  
  40.     int j = 0;
  41.     for(int i=1; i<n; i++)
  42.     {
  43.         if(arr[i] != arr[i-1])
  44.         {
  45.             arr[++j]=arr[i];
  46.         }
  47.     }
  48.  
  49.     printf("\nArray After Removing Duplicates: ");
  50.     for(int i=0;i<j+1;i++)
  51.         printf("%d ",arr[i]);
  52.  
  53.     return 0;
  54. }
Program Explanation

1. Take the number, n as input from the user.
2. Declare an array of size n.
3. Enter n elements into the array.
4. If n = 0 means there is no element in the array. Print there is no element in the array and exit.
5. Print the array elements before removing the duplicates.
6. Sort the array using the function qsort().
7. The values that needs to be passed on the function qsort() are: arr, n, sizeof(int) and call to a function cmpfunc.
8. The function cmpfunc is used to compare two values at a time in an array.
9. Declare a variable j = 0.
10. Run a for loop from i=1 to n and in each iteration check if arr[i] is equal to arr[i-1] or not.
11. If arr[i] is not equal to arr[i-1], enter the element at arr[i] to arr[++j].
12. Repeat this step till i=n.
13. Now, the array arr contains all the unique values in a sorted order.
14. print all the elements present inside the array arr.
15. Exit.

Time Complexity: O(n log(n))
The above program for removing duplicates from an array has a time complexity of O(n log(n)) as the time complexity of qsort function i.e., quicksort is O(n log(n)).

Space Complexity: O(n)
In the above program, space complexity is O(n) as array arr[] of size n has been initialized to store elements.

Runtime Test Cases

Testcase 1: In this case, the array has “8” elements, and the array elements are “9, 3, 6, 9, 5, 4, 0, and 5”.

Enter number of elements in the array: 8
Enter elements in the array: 9 3 6 9 5 4 0 5
 
Array Before Removing Duplicates: 9 3 6 9 5 4 0 5
Array After Removing Duplicates: 0 3 4 5 6 9

Testcase 2: In this case, the array has “5” elements, and the array elements are “3, 2, 3, 3, and 2”.

Enter number of elements in the array: 5
Enter elements in the array: 3 2 3 3 2
 
Array Before Removing Duplicates: 3 2 3 3 2
Array After Removing Duplicates: 2 3

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.