re

REMOVAL OF DUPLICATES FROM ORDEREDARRAY

Problem definition: To design an algorithm for removal of duplicates using array.

Problem description:

We can use array with duplicates and also array without duplicates.In both of this we can use sorted array with duplicates and sorted array without duplicates.

• Two methods:

*Array without duplicates.

*Array with duplicates.

• Two types of condition to compare the given two elements:

(1).i=1; a[i]=a[i+1];

->In this type we assign that the comparison is between the adjacent elements.

->And also this type may have the range of values in the outer bound.

(2).i=2; a[i-1]=a[i];

->In this type we assign that the current i index is compared with (i-1)th index.

->This part also have the range of values and it is supply within the array.

->Comparing with this two type of range of values (2) type of values is best choice for doing removal of duplicates.

• Purpose of usage the condition(i<n) instead of i<=n:

->Though (i<=n) condition is satisfied,no need to use this condition because that one value is count in out of range area.So,we can use the condition(i<n).

(Eg):n=3,i=2.

->Here i<n is condition is more applicable.

@.Explanations:

(1).Array without duplicates:

Consider an (eg): 10 20 30 40 50

->While comparing the elements if they are equal then it is duplicate element.Orelse if the element is not equal then update the i value after that it move on to next comparison.

(1a) Necessary steps:

->Initialize i=2;

->Check condition(i<n&&a[i-1]!=a[i])

->If it is satisfy then update the I value.

i=2

I (1). (eg) 10 _ 20 30 40 50

_ ( comparison symbol)

Here condition is true .So,there is no duplicate element,update the i value.

i=3

I(2).10 20 _ 30 40 50

Here condition is true .So,there is no duplicate element,update the i value.

i=4

I(3).10 20 30 _ 40 50

Here condition is true .So,there is no duplicate element,update the i value.

i=5

I(4).10 20 30 40 _ 50

If i is reach the last element the comparison is not done for the 4 &5 element.

So ,we have include this coding during ‘array without duplicates’:

->a[i-1]!=a[i]

->if this condition is satisfied then i is incremented to 6.

->J=i-1;//this above 6 is in out of range of array values.so,decrement the i value and assign it to ‘j’ value.

Then the result is:10 20 30 40 50

• (2).sorted array with duplicates:

Consider an (eg): 20 30 40 40 40 50

->While comparing the elements if they are equal then it is duplicate element.Orelse if the element is not equal then update the i value after that it move on to next comparison.

(2a)necessary steps:

->Initialize same as i=2;

->Then check (a[i-1]!=a[i]&&i<n).

->If it is satisfy my condition i++ the index.

i=2

I(1).20 _ 30 40 40 40 50

The condition is true because the comparing element is not equal.then update the i value.

i=3

I(2).20 30 _ 40 40 40 50

The condition is true because the comparing element is not equal.then update the i value.

i=3

I(3).20 30 40 _ 40 40 50

->The condition is false because the comparing element is equal.then no update here. It move on to next comparison

->Here we have to maintain the variable j is a unique index that have only the element which are not duplicated.It move on to next comparison.

->J=i-1//it assign the previous element which are not duplicate element by using loop.

j i=3

I(4).20 30 40 40 _ 40 50

->The condition is false because the comparing element is equal.then no update here. It move on to next comparison.

j i=4

I(5).20 30 40 40 40 _ 50 -> (1)

The condition is true because the comparing element is not equal.then update the i value.

j

20 30 40 40/50 ||40 50|| -> (2)

|| || ->virtual value.

/ -> overwrite the value.

->Here no change is happen then j (unique index) is update.

->Overwritten the last element in the place of recent j variable.(40/50).

->This means the duplicate value is removed from array.

->Then finally result is:20 30 40 50.

• Program:

Void main()

{

Int a[100],i,j,n;

Scanf(“%d”,&n);

For(i=0;i<n;i++)

Scanf(“%d”,&a[i]);

i=2;

while(i<n&&a[i-1]!=a[i])

i++;

if(a[i-1]!=a[i])

i++;

j=i-1;

while(i<n)

{

i++;

if(a[i-1]!=a[i])

{

j++;

a[j]=a[i];

}

}

n=j;

for(i=0;i<n;i++)

printf(“%d”,a[i]);

}

Applications:

#Data compression

#Text processing problems.