duplicate element removal

Question

I have tried to remove the duplicate elements from the array using c language, here I am using 3 for loops to remove the duplicate elements.

How can this optimize the code?

Are there any other simple methods to remove the duplicate elements?

Please help.

#include <stdio.h>

#define MAX_SIZE 100 // Maximum size of the array

int main()
{

 int arr[MAX_SIZE]; 
 int size;        
 int i, j, k;     


printf("Enter size of the array : ");
scanf("%d", &size);


printf("Enter elements in array : ");
for(i=0; i<size; i++)
{
    scanf("%d", &arr[i]);
}



for(i=0; i<size; i++)
{
    for(j=i+1; j<size; j++)
    {

        if(arr[i] == arr[j])
        {
         
            for(k=j; k<size; k++)
            {
                arr[k] = arr[k + 1];
            }

     
            size--;

            j--;
        }
    }
}

printf("\nArray elements after deleting duplicates : ");
for(i=0; i<size; i++)
 {
    printf("%d\t", arr[i]);
 }

return 0;
 }

Answer 1

You already have a good answer from Roland, but I'll add a few small points.

It's good practice to make every function declaration a prototype - specify the number and type of the arguments it accepts. So instead of int main(), we write int main(void) to indicated that it can only be called with no arguments.

We can reduce scope of the index variables i, j and k. For example, for (int i = 0; i < size; ++i). There's no longer a gap between declaring i and assigning its first value of 0, which reduces opportunities for error.

When we call scanf(), it returns the number of values successfully converted. That may be less than the number of values we asked for. It's important not to use values that weren't successfully written:

if (scanf("%d", &size) != 1) {
    fputs("format error", stderr);
    return 1;
}

This test also handles the case where there is an error reading from the stream, in which case scanf() returns EOF.

Answer 2

The code looks reasonably short and clear, that's good.

It's obvious that you are a beginner though since your code layout is inconsistent in a few places. Formatting the code consistently is mostly a boring task, that's why several people wrote programs to perform this formatting automatically. There are many different formatting styles, try one that fits your own liking and use that style consistently.

One of these programs is ClangFormat.

The result of formatting your code with the default settings is:

#include <stdio.h>

#define MAX_SIZE 100 // Maximum size of the array

int main() {

  int arr[MAX_SIZE];
  int size;
  int i, j, k;

  printf("Enter size of the array : ");
  scanf("%d", &size);

  printf("Enter elements in array : ");
  for (i = 0; i < size; i++) {
    scanf("%d", &arr[i]);
  }

  for (i = 0; i < size; i++) {
    for (j = i + 1; j < size; j++) {

      if (arr[i] == arr[j]) {

        for (k = j; k < size; k++) {
          arr[k] = arr[k + 1];
        }

        size--;

        j--;
      }
    }
  }

  printf("\nArray elements after deleting duplicates : ");
  for (i = 0; i < size; i++) {
    printf("%d\t", arr[i]);
  }

  return 0;
}

In this version, the indentation of each line tells the reader which pieces of the code belong together. In your original version, this was not easy to see.

To advanced programmers, the consistently formatted version looks calm and ordered, just like code should look like. Your original version instead looks chaotic. So far for the first impression.

---

At your current stage of learning to program, you probably didn't learn how to define functions yet. Functions are an important way to structure your code, so that you can highlight the interesting parts of the code. In this case, the most interesting function of the code would be "remove duplicate elements from an array, given by the first element and the size of the array". In C, this is written like this:

// Removes duplicates, returns the new size of the array.
// Keeps the order of the original elements, removing the duplicates that occur later.
static int
remove_duplicates_from_int_array(int *arr, int arr_size)
{
    // TODO: actually implement this function
}

Separating the code that removes the duplicates from the rest of the code makes it possible to test and analyze this part of the code on its own. For example you can write a standard test case:

#include <assert.h>

...

    size = 3;
    arr[0] = 1;
    arr[1] = 3;
    arr[2] = 1;

    size = remove_duplicates_from_int_array(arr, size);

    assert(size == 2);
    assert(arr[0] == 1);
    assert(arr[1] == 3);

With this code, you don't have to enter the size and the elements yourself anymore, which is a huge time-saver.

Even better would be to extract this test code into its own function:

static void
test_remove_duplicates_from_int_array(void) {
    // the code from above
}

This allows you to quickly run this test code at the start of the program, to ensure that the code still works for the basic test cases, before you even start entering your own test cases manually. Again, this saves a lot of time.

---

When you carefully inspect your code and "run" it with pen and paper, you will notice that the code reads data from outside of the array. This bug needs to be fixed before you should think about performance. Having fast and wrong code is usually worse than slow and correct code.

This bug is not easy to find when you only look at the input and output, since everything seems to work fine. The tricky thing is that reading from outside of an array invokes undefined behavior, and this means that nothing at all is guaranteed when running this program. To really run into this undefined behavior, you have to enter the array size as 100 and actually enter exactly 100 array elements, something you probably never did since it is quite an effort. Therefore, for simpler testing, you should reduce MAX_SIZE to around 5. This allows you to test the edge cases more quickly.

Except for this bug, the code looks reasonable. After you have fixed this bug, you can start thinking about making the code run faster. That's the tricky part though. As long as the array is short, your current approach is simple and easy to understand. Only if your arrays grow larger you need to get concerned about the algorithm's complexity, which is currently \$\mathcal O(\mathrm{size} \cdot \mathrm{size} \cdot \mathrm{size})\$. That is, for an array with 1000 elements, you would need a billion steps.

To design a more efficient algorithm, print out a sheet of paper with 1000 random numbers and remove the duplicates manually, asking yourself what you do in each step and why. One idea may be to sort the numbers, after which it is much easier to remove the duplicates. But then you lose the original order of the numbers, which may or may not be acceptable.

So far for a few ideas, I'm not going to solve everything for you. :)