Removing duplicate elements in array without sorting - wrong output

Question

I have been trying to write a function to remove duplicate elements in an array of ints without sorting it.

For that task, I created a function named removeDuplicateElements, which gets an array and its string, and returns a new dynamically allocated array, which is a copy of the original array with removal of all duplicates elements. This function also returns by reference the size of the new array.

I also used in my code functions which build a dynamic array and print it.

Here is my code:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void printArray(int *arr, int size);
int *buildArray(int size);
int *removeDuplicateElements(int *arr, int size, int *newSize);

void main() {
    int size,newSize;
    int *arr;
    int *newArr;

    printf("please enter a number for the size of array: ");
    scanf("%d", &size);
    printf("\nenter %d numbers: ", size);
    arr = buildArray(size);
    printf("\nthe array after removing the duplicate elements is: ");
    newArr = removeDuplicateElements(arr, size, &newSize);
    printArray(newArr, newSize);
    free(newArr);
    free(arr);
}

/* this function removes all duplicate elements in a given array */
int *removeDuplicateElements(int *arr, int size, int *newSize) {
    int *newArr;
    int count = size, i, j; 

    /* finding the new size of the original array with removal its duplicate elements */
    for (i = 1; i < size; i++) {  
        for (j = 0; j < size; j++)
            if (arr[i] == arr[j] && i != j) {
                count--;
                break;
            }
    }
    newArr = (int*)malloc(count * sizeof(int)); /* dynamically allocating the new array */

    count = 1;
    newArr[0] = arr[0];

    /*adding the elements in the new array without changing the order*/
    for (i = 1; i < size; i++) {
        for (j = 0; j < size; j++) {
            if (arr[i] == arr[j] && i != j) {
                break;
            }
            if (j == size - 1) {
                newArr[count] = arr[i];
                count++;
            }
        }
    }
    *newSize = count;     /* updating the size of the new array */
    return newArr;        /* returning the address of new array */
}

void printArray(int *arr, int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int *buildArray(int size) {
    int i;
    int *arr = (int*)malloc(size * sizeof(int));

    if (!arr) {
        printf("ERROR! Not enough memory!\n");
        exit(1);
    }

    for (i = 0; i < size; i++)
        scanf("%d", &arr[i]);

    return arr;
}

I get a wrong output for that code, and I dont understand why

For instance, for the following array with size=5 :1 1 3 1 3 I get the wrong output 1, whereas the expected outout is 1 3.

Any help would be appreciated.

Don't use void main(). Your nested loops are wrong, you are counting the same duplicate many times. Run the program in your head for {1,1,1} and see what count you get. — n. m. could be an AI
– n. m. could be an AI, Commented Aug 30, 2018 at 9:42

Chris Turner · Accepted Answer · 2018-08-30 10:24:10Z

3

You're firstly calculating the size of the new array incorrectly. For your example input, when you're looking at the first 3, it scans the whole array to see how many 3's there are and finds there are 2 and concludes it's a duplicate. It then does the exact same thing for the 2nd 3. So you end up with the size of the new array as 1.

Instead of scanning the whole array, you only want to scan the array for the elements preceding the one you're checking. So something like this.

for(i=1;i<size;i++)
{
    for (j = 0; j < i; j++)
        if (arr[i] == arr[j])
        {
            count--;
            break;
        }
}

And for the code that fills the new array has the same problem

for(i=1;i<size;i++)
{
    for (j = 0; j < i; j++)
        if (arr[i] == arr[j])
        {
            break;
        }
    if(j==i)
    {
        newArr[count++]=arr[i];
    }
}

answered Aug 30, 2018 at 10:24

Chris Turner

8,1421 gold badge16 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

DonaldT Over a year ago

thanks a lot, no it works and more important - I understand where I have done mistakes.

4386427 Over a year ago

@DonaldT It sounds as if this answer was helpful for you. If that's the case you should considering accepting it.

DonaldT Over a year ago

@4386427 I didnt know that..thank you for letting me know. I have just accepted it.

Irfan Baig · Accepted Answer · 2018-08-30 11:43:39Z

There is an alternative way of doing it, ofcourse it involves modifying the original array but this is just an alternative. Basically it involves crossing off the duplicate element by replacing it with a maximum value like 0xFFFF.

int* removeDuplicateElements(int *arr, int size, int *newSize)
{    
int *newArr;
int count = size, i, j;
int index = 0;

/*finding the new size of the original array with removal its duplicate elements*/

for(i=0;i<size;i++)
{
    for (j = i+1; j < size; j++)
        if (arr[i] == arr[j] && arr[i] != 0xFFFF)
            {
                count--;
                arr[j] = 0xFFFF;

            }

}

printf("Size is %d \n", count);

newArr = (int*)malloc(count * sizeof(int));      /*dynamically allocating the new array*/

for(i=0;i<size;i++)
{
    if(arr[i] != 0xFFFF)
    newArr[index++] = arr[i];
}

*newSize = count;     /*updating the size of the new array*/
return newArr;        /*returning the address of new array*/

}

Collectives™ on Stack Overflow

Removing duplicate elements in array without sorting - wrong output

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related