Sunday, July 8, 2007

Write code to remove duplicates in a sorted array.

There are a number of ways to remove duplicates from a sorted array. Here are a few C programs...


Method1

In this simple C program, we change the original array and also send the new size of the array back to the caller.


#include < stdio.h >

int removeDuplicates(int a[], int array_size);

// The main function
int main()
{

// Different test cases..
int my_array1[] = {1, 1, 2, 3, 5, 6, 6, 7, 10, 25, 100, 123, 123};
int my_array1_size = 13;

int my_array2[] = {1, 2, 3, 5, 6};
int my_array2_size = 5;

int my_array3[] = {1, 1, 1, 1, 1};
int my_array3_size = 5;

int my_array4[] = {123, 123};
int my_array4_size = 2;

int my_array5[] = {1, 123, 123};
int my_array5_size = 3;

int my_array6[] = {123, 123, 166};
int my_array6_size = 3;

int my_array7[] = {1, 2, 8, 8 , 24, 60, 60, 60, 60, 75, 100, 100, 123};
int my_array7_size = 13;


my_array1_size = removeDuplicates(my_array1, my_array1_size);
my_array2_size = removeDuplicates(my_array2, my_array2_size);
my_array3_size = removeDuplicates(my_array3, my_array3_size);
my_array4_size = removeDuplicates(my_array4, my_array4_size);
my_array5_size = removeDuplicates(my_array5, my_array5_size);
my_array6_size = removeDuplicates(my_array6, my_array6_size);
my_array7_size = removeDuplicates(my_array7, my_array7_size);

return(0);
}


// Function to remove the duplicates
int removeDuplicates(int a[], int array_size)
{
int i, j;

j = 0;


// Print old array...
printf("\n\nOLD : ");
for(i = 0; i < array_size; i++)
{
printf("[%d] ", a[i]);
}


// Remove the duplicates ...
for (i = 1; i < array_size; i++)
{
if (a[i] != a[j])
{
j++;
a[j] = a[i]; // Move it to the front
}
}

// The new array size..
array_size = (j + 1);


// Print new array...
printf("\n\nNEW : ");
for(i = 0; i < array_size; i++)
{
printf("[%d] ", a[i]);
}
printf("\n\n");



// Return the new size...
return(j + 1);
}




And here is the output...


OLD : [1] [1] [2] [3] [5] [6] [6] [7] [10] [25] [100] [123] [123]
NEW : [1] [2] [3] [5] [6] [7] [10] [25] [100] [123]


OLD : [1] [2] [3] [5] [6]
NEW : [1] [2] [3] [5] [6]


OLD : [1] [1] [1] [1] [1]
NEW : [1]


OLD : [123] [123]
NEW : [123]


OLD : [1] [123] [123]
NEW : [1] [123]


OLD : [123] [123] [166]
NEW : [123] [166]


OLD : [1] [2] [8] [8] [24] [60] [60] [60] [60] [75] [100] [100] [123]
NEW : [1] [2] [8] [24] [60] [75] [100] [123]





Method2

If we dont want to change the input array and just want to print the array without any duplicates, the solution is very simple. Check out the removeDuplicatesNoModify() function in the program below. It keeps a track of the most recently seen number and does not print any duplicates of it when traversing the sorted array.



#include < stdio.h >

void removeDuplicatesNoModify(int my_array[], int my_array1_size);
void print_array(int array[], int array_size, int current_pos, int dup_start, int dup_end);


// The main function
int main()
{
// Different inputs...
int my_array1[] = {1, 1, 2, 3, 5, 6, 6, 7, 10, 25, 100, 123, 123};
int my_array1_size = 13;

int my_array2[] = {1, 2, 3, 5, 6};
int my_array2_size = 5;

int my_array3[] = {1, 1, 1, 1, 1};
int my_array3_size = 5;

int my_array4[] = {123, 123};
int my_array4_size = 2;

int my_array5[] = {1, 123, 123};
int my_array5_size = 3;

int my_array6[] = {123, 123, 166};
int my_array6_size = 3;

int my_array7[] = {1, 2, 8, 8 , 24, 60, 60, 60, 60, 75, 100, 100, 123};
int my_array7_size = 13;


removeDuplicatesNoModify(my_array1, my_array1_size);
removeDuplicatesNoModify(my_array2, my_array2_size);
removeDuplicatesNoModify(my_array3, my_array3_size);
removeDuplicatesNoModify(my_array4, my_array4_size);
removeDuplicatesNoModify(my_array5, my_array5_size);
removeDuplicatesNoModify(my_array6, my_array6_size);
removeDuplicatesNoModify(my_array7, my_array7_size);

return(0);
}



// This function just prints the array without duplicates.
// It does not modify the original array!

void removeDuplicatesNoModify(int array[], int array_size)
{
int i, last_seen_unique;

if(array_size <= 1){return;}

last_seen_unique = array[0];

printf("\n\nOld : ", array_size);

for(i = 0; i < array_size; i++)
{
printf("[%2d] ", array[i]);
}

printf("\nNew : ", array_size);

printf("[%2d] ", array[0]);
for(i=1; i < array_size; i++)
{
if(array[i]!=last_seen_unique)
{
printf("[%2d] ", array[i]);
last_seen_unique = array[i];
}
}

printf("\n");
}




And here is the output..

Old : [ 1] [ 1] [ 2] [ 3] [ 5] [ 6] [ 6] [ 7] [10] [25] [100] [123] [123]
New : [ 1] [ 2] [ 3] [ 5] [ 6] [ 7] [10] [25] [100] [123]


Old : [ 1] [ 2] [ 3] [ 5] [ 6]
New : [ 1] [ 2] [ 3] [ 5] [ 6]


Old : [ 1] [ 1] [ 1] [ 1] [ 1]
New : [ 1]


Old : [123] [123]
New : [123]


Old : [ 1] [123] [123]
New : [ 1] [123]


Old : [123] [123] [166]
New : [123] [166]


Old : [ 1] [ 2] [ 8] [ 8] [24] [60] [60] [60] [60] [75] [100] [100] [123]
New : [ 1] [ 2] [ 8] [24] [60] [75] [100] [123]





Method3

Here is a slightly compilcated, but more visual version of the removeDuplicates() function. It shrinks the original array as and when it find duplicates. It is also optimized to identify continuous strings of duplicates and eliminate them at one shot.




#include < stdio.h >

void removeDuplicates(int array[], int *array_size) ;
void print_array(int array[], int array_size, int current_pos, int dup_start, int dup_end);


// The main function
int main()
{
// Different inputs...
int my_array1[] = {1, 1, 2, 3, 5, 6, 6, 7, 10, 25, 100, 123, 123};
int my_array1_size = 13;

int my_array2[] = {1, 2, 3, 5, 6};
int my_array2_size = 5;

int my_array3[] = {1, 1, 1, 1, 1};
int my_array3_size = 5;

int my_array4[] = {123, 123};
int my_array4_size = 2;

int my_array5[] = {1, 123, 123};
int my_array5_size = 3;

int my_array6[] = {123, 123, 166};
int my_array6_size = 3;

int my_array7[] = {1, 2, 8, 8 , 24, 60, 60, 60, 60, 75, 100, 100, 123};
int my_array7_size = 13;

removeDuplicates(my_array1, &my_array1_size);
removeDuplicates(my_array2, &my_array2_size);
removeDuplicates(my_array3, &my_array3_size);
removeDuplicates(my_array4, &my_array4_size);
removeDuplicates(my_array5, &my_array5_size);
removeDuplicates(my_array6, &my_array6_size);
removeDuplicates(my_array7, &my_array7_size);

return(0);
}




// Changes the original array and resets the size of the array if duplicates
// have been removed.

void removeDuplicates(int array[], int *array_size)
{
int i, j, k, l;
int current_pos;
int dup_start;
int dup_end;

printf("\nInitial array (size : [%d])\n\n", *array_size);
for(i = 0; i < *array_size; i++)
{
printf("[%2d] ", array[i]);
}
printf("\n\n\n------------------------------------------------\n");


if(*array_size == 1){return;}


// Remove the dups...
for (i = 0; (i < *array_size); i++)
{
//Start with the next element in the array and check if its a duplicate...
for(j = i+1; (j < *array_size); j++)
{
if(array[i]!=array[j])
{
// No duplicate, just continue...
break;
}
else
{
// The next element is a duplicate.
// See if there are more duplicates, as we want to optimize here.
//
// That is, if we have something like
//
// Array : [1, 1, 1, 2]
//
// then, we want to copy 2 directly in the second position and reduce the
// array to
//
// Array : [1, 2].
//
// in a single iteration.

current_pos = i;
dup_start = j;

j++;

while((array[i]==array[j]) && (j < *array_size))
{
j++;
}

dup_end = j-1;

print_array(array, *array_size, current_pos, dup_start, dup_end);

// Now remove elements of the array from "dup_start" to "dup_end"
// and shrink the size of the array.

for(k = (dup_end + 1), l = dup_start ; k < *array_size;)
{
array[l++]=array[k++];
}

// Reduce the array size by the number of elements removed.
*array_size = *array_size - (dup_end - dup_start + 1);

}
}
}

printf("\n\n------------------------------------------------");
printf("\n\nFinal array (size : [%d])\n\n", *array_size);
for(i = 0; i < *array_size; i++)
{
printf("[%2d] ", array[i]);
}
printf("\n\n");

}




// This function prints the array with some special pointers to the numbers that
// are duplicated.
//
// Dont bother too much about this function, it just helps in understanding
// how and where the duplicates are being removed from.

void print_array(int array[], int array_size, int current_pos, int dup_start, int dup_end)
{
int i;

printf("\n\n");

for(i = 0; i < array_size; i++)
{
printf("[%2d] ", array[i]);
}

printf("\n");

for(i = 0; i < array_size; i++)
{
if((i == current_pos) ||
(i == dup_start && i == dup_end) ||
((i == dup_start || i == dup_end) && (dup_start != dup_end)))
{
printf(" ^ ");
}
else
{
printf(" ");
}
}

printf("\n");

for(i = 0; i < array_size; i++)
{
if((i == current_pos) ||
(i == dup_start && i == dup_end) ||
((i == dup_start || i == dup_end) && (dup_start != dup_end)))
{
printf(" | ");
}
else
{
printf(" ");
}
}

printf("\n");

for(i = 0; i < array_size; i++)
{
if(i == current_pos)
{
printf(" C ");
}
else if(i == dup_start && i == dup_end)
{
printf(" S/E ");
}
else if((i == dup_start || i == dup_end) && (dup_start != dup_end))
{
if(i == dup_start)
{
printf(" S--");
}
else
{
printf("--E ");
}
}
else if(i > dup_start && i < dup_end)
{
printf("-----");
}
else
{
printf(" ");
}
}

}





And here is the output (for one of the inputs)...


C - Current position.
S - Start of duplicates.
E - End of duplicates.




Old : [ 1] [ 2] [ 8] [ 8] [24] [60] [60] [60] [60] [75] [100] [100] [123]

-------------------------------------------------------------------------
[ 1] [ 2] [ 8 (C) ] [ 8 (S/E) ] [24] [60] [60] [60] [60] [75] [100] [100] [123]


[ 1] [ 2] [ 8] [24] [60 (C)] [60 (S)] [60 (E)] [60] [75] [100] [100] [123]


[ 1] [ 2] [ 8] [24] [60] [75] [100 (C)] [100 (S/E)] [123]

-------------------------------------------------------------------------
New : [ 1] [ 2] [ 8] [24] [60] [75] [100] [123]



If there are other elegant methods of removing duplicate numbers from an array, please let me know!.

52 comments:

preetriti said...

Great Help ... this is the way we need to think about a question with all the possibilities

Bharath said...

This can be done by storing all the elements in an hash and just removing the key values.

Anonymous said...

Bharath, that's highly dependent on the hashing function. If the hashing function is such that there are collisions between items that are not, in reality, duplicates, unintended omissions would result.

Since the array is sorted, merely looping through the array to create a new one requires O(n). The hashing approach also requires O(n) to hash all of the elements, but it has the added complexity of dealing with the aforementioned collisions.

As such, it's likely more time efficient to use the suggested (simpler) methods.

Anonymous said...

This above coding is very useful..but i need a duplicates removing program when the duplicates numbers are present at different position in the array....

Anonymous said...

I'm the sort of guy who loves to try different things. Right now I'm fabricating my hold photovoltaic panels. I am making it all alone without the help of my men. I am utilizing the internet as the only way to acheive that. I ran across a truly amazing website that explains how to make solar panels and so on. The web site explains all the steps required to solar panel construction.

I'm not really sure about how correct the information given there iz. If some experts over here who have experience with these things can have a look and give your feedback in the thread it would be awesome and I'd really treasure it, because I really take an interest in solar panel construction.

Tnx for reading this. U guys are great.

Shams Sheikh said...

int main ()
{
int a[]={1,1,1,2,3,4,4,5,6,7,8,9,10};
for(int i=0;i<13;i++)
{
if(a[i]^a[i+1])
cout<<a[i]<<" ";
else
continue;
}
}

Anonymous said...

Hi

I like this post:

You create good material for community.

Please keep posting.

Let me introduce other material that may be good for net community.

Source: Construction interview questions

Best rgs
Peter

Anonymous said...

More Easy Way to
Remove Duplicate Elements From Array With Dynamic Array Size in C or C++

Sorry !!
Code don't Showing here !

To Read Details & Get CODE

Please, Click Here
Or,Go to :- http://mysharewire.blogspot.com/

Vikash Mehta said...

using tree will be a good idea and effective as well..... just ignore duplicate entry while inserting

As search and insert will be fast.

Here is the workable code:

#include
#include


typedef struct node{
int data;
struct node *left;
struct node *right;
}NODE;

void printTree(NODE* );
NODE* AddInTree(NODE*, int);

int main()
{
NODE *root = NULL;
NODE *temp = NULL;
int array[11]={1,1,4,5,3,5,4,8,9,1};
int i=0;

//printing old Array lenght
while(array[i] != '\0') printf("%d, ", array[i++]);
printf("\n Old array length is:%d and values are",i);


//Add value in tree and remove duplicate
i =0;
while(array[i] != '\0')
{
temp = root;
root = AddInTree(temp, array[i]);
i++;
}

printf("\n printing tree element");

//print new TREE element
temp = root;
printTree(temp);
getchar();
return 0;
}

NODE* AddInTree(NODE *temp, int data)
{

int dup = 0;
NODE *bkp = temp;
NODE *node = (NODE*)malloc(sizeof(NODE));
node->data = data;
node->left = NULL;
node->right = NULL;


if(bkp == NULL)
{
node->left = NULL;
node->right=NULL;
return node;
}
else
{
while(bkp != NULL)
{
if(bkp->data == data)
{
printf("\n dup found:%d",data);
dup=1;
break;
}
if(data <= bkp->data )
{
if(bkp->left != NULL)
bkp = bkp->left;
else
{
bkp->left = node;
break;
}
}
else
{
if(bkp->right != NULL)
bkp = bkp->right;
else
{
bkp->right =node;
break;
}
}

}

}//en of ELSE

return temp;
}

void printTree(NODE *root)
{
if(root == NULL) return;
else
{
printf("%d, ",root->data);
printTree(root->left);
printTree(root->right);
}
}

Anonymous said...

Is there a way to apply this for strings?

Anonymous said...

getsize_type(int)) #define getsize_var(x) ((char *)(&(x) + 1) - (char *)&(x)) #define getsize_type(type) ( (char*)((type*)(1) + 1) - (char*)((type *)(1)))

Anonymous said...

static void Main(string[] args)
{
int[] arr = { 2,2};
int[] brr= new int[45];
int i = 0, k = 0;
brr[k++] = arr[0];
while (i < arr.Length-1)
{
if (arr[i] == arr[++i])
continue;
brr[k++] = arr[i];
}
if (arr[i - 1] == arr[i] && arr[i-1]!=brr[k-1])
brr[k] = arr[i];

foreach (int j in brr)
Console.Write(j);

Anonymous said...

check ur first program by passing this you will get wrong result your logic is wrong
OLD :
1 1 1 2 2 3 4 5 6 6 3
NEW :
1
2
3
4
5
6
3

Anonymous said...

buy tramadol online where to buy tramadol online safely - tramadol online no prescription usa

Anonymous said...

generic xanax online xanax drug usage - get over xanax withdrawal

Anonymous said...

alprazolam without prescription xanax 93833 - valium vs xanax drug test

Anonymous said...

tramadol online no prescription tramadol 50 mg for ultram - zydol 50 mg tramadol hydrochloride

Anonymous said...

buy tramadol online can tramadol overdose fatal - tramadol hcl lethal dose

Anonymous said...

xanax order no prescription buy alprazolam 1mg - xanax drug pics

Anonymous said...

buy tramadol online tramadol 50 mg and alcohol - tramadol no prescription overseas

Anonymous said...

generic xanax xanax and zanaflex drug interactions - what does xanax and alcohol do to the body

Anonymous said...

buy carisoprodol carisoprodol 350 mg overnight - carisoprodol 350 mg alcohol

Anonymous said...

buy tramadol tramadol dosage limits - tramadol 20mg dogs

Anonymous said...

cheap xanax no prescription xanax generic brand name - xanax tablets 0.25 mg

Anonymous said...

buy tramadol online is tramadol hcl 50 mg an opiate - tramadol er

Anonymous said...

generic xanax xanax 2mg sunset yellow - xanax effects nervous system

Anonymous said...

xanax online xanax generic price - generic xanax 3mg pills

Anonymous said...

tramadol without prescription buy tramadol online no prescription usa - buy tramadol in dubai

Anonymous said...

generic cialis no prescription buy cialis without rx - cialis kaufen

Anonymous said...

buy tadalafil cialis online discreet - generic cialis levitra

Anonymous said...

http://landvoicelearning.com/#62431 tramadol 325 dosage - buy tramadol online overnight delivery

Anonymous said...

http://buytramadolonlinecool.com/#56411 help for tramadol addiction - buy tramadol online safe

Anonymous said...

buy tramadol tramadol overdose what to do - tramadol 50 mg good

Anonymous said...

buy tramadol tramadol 50 mg purchase - tramadol hcl 150

Anonymous said...

http://landvoicelearning.com/#30896 tramadol dosage weight - buy tramadol online legally

Anonymous said...

Really no matter if someone doesn't be aware of after that its up to other users that they will assist, so here it happens.

My website; Graduate certificates online
Also see my webpage :: graduate certificate

Anonymous said...

buy tramadol online where can i purchase tramadol with a mastercard - buy tramadol online with credit card

Anonymous said...

http://ranchodelastortugas.com/#50238 xanax withdrawal 1mg per day - xanax saliva drug test

Anonymous said...

I truly appreciate this post. I have been
looking everywhere for this! Thank goodness I found it
on Bing. You've made my day! Thank you again!

Review my webpage: redeem Psn codes

Anonymous said...

This design is incredible! You definitely
know how to keep a reader amused. Between your wit and your videos, I was almost moved to
start my own blog (well, almost...HaHa!) Excellent job. I really loved what you
had to say, and more than that, how you presented it.
Too cool!

My web site the tao of dating for women

Anonymous said...

It's amazing to go to see this site and reading the views of all colleagues concerning this piece of writing, while I am also eager of getting knowledge.

Also visit my webpage - password hack

Anonymous said...

Aw, this was a really nice post. Finding the time and actual effort
to create a good article… but what can I say… I hesitate a
whole lot and don't seem to get nearly anything done.

My homepage - best ptc sites

Anonymous said...

Good post. I learn something new and challenging on sites I stumbleupon every
day. It's always interesting to read through articles from other writers and practice a little something from their sites.

My site ... Its About Time Grindstone Mattseh

Anonymous said...

Have you ever thought about writing an e-book or guest authoring on other websites?
I have a blog centered on the same information you discuss
and would love to have you share some stories/information.
I know my visitors would enjoy your work. If you're even remotely interested, feel free to shoot me an e mail.

My site cs 1.6 Aimbot

Anonymous said...

where to buy tramadol online buy tramadol online cheap - buy generic tramadol

Anonymous said...

I got this web site from my pal who told me on the topic of this
web page and now this time I am browsing this website and reading
very informative posts here.

Here is my page: tao of badass

Anonymous said...

tramadol no rx buy tramadol no prescription - buy tramadol cod

Anonymous said...

Motorola Atrix a couple of 4g Mb865 Jailbroke Gsm Quad
Wedding ring Android

My website; Panasonic PT-AE7000

Anonymous said...

PSN Code Card 100$

Here is my blog post - homepage

Anonymous said...

Thoughts on Home Secureness Essentials

My web blog :: gloss

Esdee said...

#include

using namespace std;

//remove duplicates from sorted array

int main()
{
int a[] = {1,2,3,3,3,5,6,6,8,8,8,8,9};
int size = sizeof(a)/sizeof(int);
int ai = 0, i = 0;
while (ai < size)
{
while (a[ai] == a[ai+1])
{
++ai;
}

++ai;
a[i+1] = a[ai];
++i;
}
for (int j=0;j < i; ++j) {
cout << a[j] << endl;
}

return 0;
}

Anonymous said...

e cig reviews, electronic cigarette, electronic cigarettes reviews, ecigarette, e cig forum, e cigarette