Remove duplicate numbers in an array in C:

Question

#include <stdio.h>

int main()
{
    int array[20], t = 0; //20-t is the new size of array.

    for(int i = 0; i<20; i++)
        scanf("%d", &array[i]);

    for(int i = 0; i<20-t; i++)
    {
        for(int j = i+1; j<20-t; j++)
        {
            if(array[i] == array[j])
            {
                for(int z = j; z<20-t; z++)
                    array[z] = array[z+1];//shift numbers.
                    t++; 
                    i = -1;
            }
        }
    }
}

This program works fine but I am not sure why it does when i = -1 but not when i = 0? I would also like to know the complexity of this code.

for(int i = 0; i<20-t; i++)
    printf("%d ", array[i]); //Array after duplicates have been removed.
    return 0;
}

the posted code has several instances of the 'magic' number 20. This makes the code much more difficult to understand, debug and maintain. Suggest using #define to give the 'magic' number a meaningful name and using that meaningful name throughout the code — user3629249
– user3629249, Commented Nov 23, 2015 at 14:40

Vlad from Moscow · Accepted Answer · 2015-11-21 17:23:09Z

4

If you write the program the following way

#include <stdio.h>

#define N   20

int main( void )
{
    int a[N];
    int n;
    int i;

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

    n = 0;
    for ( i = 0; i < N; i++ )
    {
        int j = 0;
        while ( j < n && a[i] != a[j] ) ++j;
        if ( j == n ) a[n++] = a[i];
    }

    for ( i = 0; i < n; i++ ) printf( "%d ", a[i] );
    printf( "\n" );

    return 0;
}

then the complexity of the algorithm will be O( N ^ 2 ).

As for your algorithm then its complexity is O( N ^ 3 ).

That is you approach is less efficient.

answered Nov 21, 2015 at 17:23

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

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

Comments

simpel01 · Accepted Answer · 2015-11-21 16:54:10Z

1

First of all your inner loop access elements in [z, 20-t+1], which is 1 element beyond the array. The 'shift numbers' loop should be:

for(int z = j; z<20-t-1; z++)
    array[z] = array[z+1];//shift numbers.

To reply your question, it works with i = -1 because i is going to be incremented by the for-j loop. Therefore it will be 0 next iteration (and not 1, thereby skipping 1 element).

Said that, what you need to do is decrement the j iterator instead, i.e.:

t++; --j;

It will run faster!

answered Nov 21, 2015 at 16:54

simpel01

1,78212 silver badges13 bronze badges

Collectives™ on Stack Overflow

Remove duplicate numbers in an array in C:

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related