Here is the C program to delete duplicate elements from a sorted array. Given a sorted integer array of length N. Array elements are sorted in increasing order(inputArray[i] <= inputArray[j] for every i < j). We have to delete duplicate elements from array and print unique elements of the array.
For Example
Sorted array containing duplicate elements : 1 2 2 2 4 4 7 8 9 9
Output array containing only unique elements : 1 2 4 7 8 9
Points to Remember
As the array is sorted, all duplicate elements must exist in adjacent positions.
For Example
In sorted array 1 2 2 2 3 4 4 5 6 7 7 7, all instances of 2, 4, and 7 are in adjacent positions. We will use this fact in below program to delete duplicate elements.
As the array is sorted, all duplicate elements must exist in adjacent positions.
For Example
In sorted array 1 2 2 2 3 4 4 5 6 7 7 7, all instances of 2, 4, and 7 are in adjacent positions. We will use this fact in below program to delete duplicate elements.
Algorithm to delete duplicate elements from a sorted array
Let inputArray be an array of length N, and readIndex and writeIndex are two integer variables to store index references.
Let inputArray be an array of length N, and readIndex and writeIndex are two integer variables to store index references.
- In a sorted array, all duplicate elements must exist in adjacent positions.
- At any instant, all element to the left of writeIndex are unique.
- inputArray[writeIndex] is always the last unique element added.
- We will traverse inputArray using using readIndex. If inputArray[readIndex] is not equal to inputArray[writeIndex], then inputArray[readIndex] is not same as the last unique element added. Hence, add inputArray[readIndex] in set of unique elements.
- At the end of traversal, we will get all unique elements between index 0 to writeIndex.
C program to delete duplicate elements from a sorted array
#include <stdio.h>
int main(){
int inputArray[500], elementCount, counter;
int readIndex, writeIndex = 0;
printf("Enter number of elements in array: ");
scanf("%d", &elementCount);
printf("Enter %d numbers in increasing order \n", elementCount);
for(counter = 0; counter < elementCount; counter++){
scanf("%d", &inputArray[counter]);
}
for(counter = 1; counter < elementCount; counter++){
if(inputArray[counter] < inputArray[counter -1]){
printf("Invalid Input: elements not in increasing order\n");
return 1;
}
}
for(readIndex=1; readIndex < elementCount; readIndex++){
if(inputArray[readIndex] != inputArray[writeIndex]){
writeIndex++;
inputArray[writeIndex] = inputArray[readIndex];
}
}
/* Print unique element */
printf("Unique Elements\n");
for(counter = 0; counter < writeIndex + 1; counter++){
printf("%d ", inputArray[counter]);
}
return 0;
}
Program Output
Enter number of elements in array: 8 Enter 8 numbers in increasing order 0 0 1 2 2 2 3 7 Unique Elements 0 1 2 3 7
Related Topics