Removing duplicates from a sorted array in c++

Question

I am trying to remove the duplicates from sorted array.Code is giving correct output for one test case but fails to give correct output for multiple test cases.I am getting correct output with other methods but what is wrong with this method? How can I solve this problem?

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
    // your code goes here
    int t;
    cin>>t;
    
    while(t--){
    
    int n;
    cin>>n;
    int a[n],i,k,temp,count;
    
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    
    sort(a,a+n);
   
    count=0;
    for(i=0;i<n;i++){
        
        if(a[i-1]-a[i]==0){
            
            temp = a[i];
            count++;
            for(k=i;k<n;k++){
                a[k] = a[k+1];  
            }
            
        }   
    }
    
    for(i=0;i<n-count;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    
        
    }
    
}

I stopped reading after 3 strikes: `#include` then `using namespace std;` then finally `int a[n]`. Please consider starting with an introductory C++ book instead of learning to code using hackerrank or leetcode — Cory Kramer, Oct 26 '21 at 17:19
[Why should I not #include ?](https://stackoverflow.com/q/31816095/3422102) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/364696) — David C. Rankin, Oct 26 '21 at 17:23
I think a new strike should be people who post code whose output depends on input from std::cin. Basically if you want to get an answer from SO there is never a good reason to post code that uses std::cin unless your question is somehow about std::cin. — jwezorek, Oct 26 '21 at 17:23
[Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) — Ted Lyngmo, Oct 26 '21 at 17:25
Well if it runs at all - I am a penguin. Have to see the results myself. UB is fun in free time — Eugene Anisiutkin, Oct 26 '21 at 17:29
Note: Online judging/competition sites are not intended to teach programming and should not be used as an educational tool. They can be fun or practice once you already have a good grasp on the language. Competition code is not written to be educational readable, or an example of good software. It's only goal is to run fast and produce a result under ideal circumstances. — user4581301, Oct 26 '21 at 17:31
Side note: Sometimes the best way to remove items from a data set is to not put them in the set in the first place. — user4581301, Oct 26 '21 at 17:34

Vlad from Moscow · Answer 1 · 2021-10-26T17:48:16.950

Variable length arrays like this

int a[n],i,k,temp,count;

is not a standard C++ feature. Instead you should use the standard container std::vector<int>.

This if statement

if(a[i-1]-a[i]==0){

invokes undefined behavior when i is equal to 0 due to the expression a[i-1].

The same problem exists in this for loop

        for(k=i;k<n;k++){
            a[k] = a[k+1];  
        }

when k is equal to n - 1 due to the expression a[k+1].

Also it is inefficient to copy all elements after the found duplicated element each time when such an element is found.

Pay attention to that there is the standard algorithm std::unique that can be used instead of your loops.

If to use the for loop then you may implement something like the following

#include <iostream>

int main() 
{
    int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
    const size_t N = sizeof( a ) / sizeof( *a );
    
    size_t n = 0;
    
    for ( size_t i = 0; i < N; i++ )
    {
        if ( i == 0 || a[i] != a[n-1] )
        {
            if ( i != n  ) a[n] = a[i];
            ++n;
        }
    }
    
    for ( size_t i = 0; i < n; i++ )
    {
        std::cout << a[i] << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

The program output is

1 2 3 4 5

If to use the standard algorithm std::unique then the solution will be simpler because there is no need to write your own for loop.

#include <iostream>
#include <iterator>
#include <algorithm>

int main() 
{
    int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };

    auto last = std::unique( std::begin( a ), std::end( a ) );
    
    for ( auto first = std::begin( a ); first != last; ++first )
    {
        std::cout << *first << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

The program output is the same as shown above that is

1 2 3 4 5

score 0 · Answer 2 · answered Oct 26 '21 at 17:31

I see two major problems with your code, both are out-of-bounds reads from an array:

if(a[i-1]-a[i]==0) will at one point be called with i==0, accessing element a[-1].

And here:

for(k=i;k<n;k++){
   a[k] = a[k+1];  
}

in the last loop iteration, when k == n-1 array element a[n] will be accessed, which is also an out-of-bounds access.

Removing duplicates from a sorted array in c++

2 Answers2