- Write a C program to delete duplicate elements from a sorted array.
- Write a C program to print unique elements of an array
Given an 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
/*
* C Program to delete duplicate elements from an sorted array
*/
#include <stdio.h>
#include <conio.h>
int main(){
int inputArray[500], elementCount, counter;
int readIndex, writeIndex;
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]);
}
/* Input Validation
* Input Elements must be in increasing order
*/
for(counter = 1; counter < elementCount; counter++){
if(inputArray[counter] < inputArray[counter -1]){
printf("Invalid Input: elements not in increasing order \n");
return 1;
}
}
/*
* All the elemets before writeIndex are unique.
* readIndex scan elements from left to write and
* tries to find a duplicate element.
*/
for(readIndex=1, writeIndex=0; 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]);
}
getch();
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