In this blog post, we learn how to write a C program to remove duplicates from sorted array? So here we will write a C program to remove duplicates from sorted array. Suppose ‘arr’ is a sorted integer array of size N and task to remove the duplicates elements from the array in such way that each element appears only once.
Example,
Input array: int arr[] = {1, 1, 1, 3, 5, 5, 7}; Output array: {1, 3, 5, 7};
Note: Because the input array is sorted so duplicates are always adjacent.
Solution 1: Brute Force
It is the simplest solution to remove duplicate elements in a given array. In which you need to create an intermediate temporary array of size N (size of input array).
As we know that in a sorted array all duplicates are always adjacent. So now need to compare the input array elements with their adjacent. If they are equal that means the duplicate element is present in the input array. So to avoid duplicate elements we only copy the elements in the intermediate array which is not matched with their adjacent elements.
After traversing the whole array we will copy all the elements of the intermediate array back to the original array and return the original array.
#include //Calculate array size #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) int removeDuplicates(int arr[], int array_size) { //intermediate temp array int temp[array_size]; unsigned int uniqueArrayLen = 0; //if array is empty // or contains a single element if (array_size <= 1) { uniqueArrayLen = array_size; } else { unsigned int i =0; for (i=0; i<array_size-1; i++) { // If current element is not equal // to adjacent element then store that // current element in temp array if (arr[i] != arr[i+1]) { temp[uniqueArrayLen++] = arr[i]; } } // Store the last element as whether // it is unique or repeated, it hasn't // stored previously temp[uniqueArrayLen++] = arr[array_size-1]; //Now copy temp array in original array for (i=0; i<uniqueArrayLen; i++) { arr[i] = temp[i]; } } return uniqueArrayLen; } int main() { int arr[] = {1, 1, 1, 3, 5, 5, 7}; int i = 0; //get array size int arr_size = ARRAY_SIZE(arr); unsigned int uniqueArrayLen = removeDuplicates(arr, arr_size); //print unique array for (i=0; i<uniqueArrayLen; i++) { printf("%d ", arr[i]); } return 0; }
Output:
output array contains {1, 3, 5, 7};
If you want to learn more about the C language, you can check this course, Free Trial Available.
You can see in the above method we are using an extra temporary array. If you want, you can save the extra space by maintaining separate index. The logic will be same as discuss in the above method. Let’s see the codeĀ
#include <stdio.h> //Calculate array size #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) int removeDuplicates(int arr[], int array_size) { unsigned int uniqueArrayLen = 0; //if array is empty // or contains a single element if (array_size <= 1) { uniqueArrayLen = array_size; } else { unsigned int i =0; for (i=0; i<array_size-1; i++) { // If current element is not equal // to adjacent element then store that // current element in temp array if (arr[i] != arr[i+1]) { arr[uniqueArrayLen++] = arr[i]; } } // Store the last element as whether // it is unique or repeated, it hasn't // stored previously arr[uniqueArrayLen++] = arr[array_size-1]; } return uniqueArrayLen; } int main() { int arr[] = {1, 1, 1, 3, 5, 5, 7}; int i = 0; //get array size int arr_size = ARRAY_SIZE(arr); unsigned int uniqueArrayLen = removeDuplicates(arr, arr_size); //print unique array for (i=0; i<uniqueArrayLen; i++) { printf("%d ", arr[i]); } return 0; }
Output:
output array contains {1, 3, 5, 7};
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- C program to find the Median of two sorted arrays of different sizes.
- C Program to find first and last position of element in sorted array
- Write C program to find the missing number in a given integer array of 1 to n
- C program to find the most popular element in an array
- Find the largest and smallest element in an array using C programming.
- C program to find even occurring elements in an array of limited range
- 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.
- C program to find odd occurring elements in an array of limited range
- 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?