To remove duplicate elements in an array and only show unique one

Divyam 0
Viewed 76

I made a program to remove duplicate elements in an array, but it is not working correctly. Can someone help me with it? When I input 1,1,1,2,3 it displays 1,1,2,3.

It works fine with other inputs, but only shows an error when I enter input with multiple 1s.

//To remove duplicacy of the elements
#include<iostream>
using namespace std;

int main()
{
    cout<<"Enter the number of elements in your array:"<<endl;
    int s;
    cin>>s;
    int arr[s];
    for (int i=0;i<s;i++)
    {
        cout<<"Enter the element at position "<<i<<endl;
        cin>>arr[i];
    }
    cout<<"Your array is"<<endl;
    for (int i=0;i<s;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    int count=0;
    for(int i=0;i<s-count;i++)
    {
        for(int j=i+1;j<s-count;j++)
        {
            if (arr[i]==arr[j])
            {
                for(int i=j;i<s-count;i++)
                {
                    arr[i]=arr[i+1];
                }
                count++;
            }
        }
    }

    cout<<"Your array after removing duplicacy now is"<<endl;
    for (int i=0;i<s-count;i++)
        {
            cout<<arr[i]<<" ";
        }
    return 0;
}
nested-loops for-loop arrays algorithm c++
4 Answers

In these nested for loops

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

if the array has or example three adjacent elements with the same value then after this loop

for(int i=j;i<s-count;i++)
{
    arr[i]=arr[i+1];
}

there will be two adjacent elements. But as the index i is incremented in the outer for loop then the second adjacent element will stay in the array because only elements after it are traversed in the second for loop.

Pay attention to that variable length arrays are not a standard C++ feature. Instead use standard container std::vector.

Actually the used approach is inefficient because all elements starting from the found duplicate element are moved. A more efficient approach can look the following way as shown in the demonstration program below.

#include <iostream>
#include <vector>
#include <iterator>

int main()
{
    std::vector<int> v = { 1, 1, 1, 2, 3 };

    for (const auto &item : v)
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';

    size_t k = 0;
    for (size_t i = 0; i < v.size(); i++)
    {
        size_t j = 0;
        while (j != k && v[j] != v[i]) j++;

        if (j == k)
        {
            if ( k != i )
            {
                v[k] = v[i];
            }
            ++k;
        }
    }

    if (k != v.size())
    {
        v.erase( std::next( std::begin( v ), k ), std::end( v ) );
    }

    for (const auto &item : v)
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
}

The program output is:

1 1 1 2 3
1 2 3

Of course instead of using indices and the subscript operator it is better to use iterators.

For example

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

int main()
{
    std::vector<int> v = { 1, 1, 1, 2, 3 };

    for (const auto &item : v)
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';

    auto result = std::begin( v );

    for ( auto current = std::begin( v ), last = std::end( v ); current != last; ++current )
    {
        if (std::find( std::begin( v ), result, *current ) == result)
        {
            if (result != current)
            {
                *result = *current;
            }
            ++result;
        }
    }
        

    v.erase( result, std::end( v ) );

    for (const auto &item : v)
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
}
Vlad from Moscow0

Basically, the problem was with the operation in your deletion loops, when you are deleting an element in the array, you need to decrement the size accordingly.

for (int i = 0; i < s; ++i)
{
    for (int j = i + 1; j < s;)
    {
        if (arr[i] == arr[j])
        {
            for (int k = j; k < s - 1; ++k)
                arr[k] = arr[k + 1];
            --s;
        }
        else
            ++j;
    }
}
Satyam Raj0

Here is the problematic section:

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

The problem is that i always moves which makes any nonunique cosecutive sequence of length > 2 undetectable. Here is the replacement, adopted from the example implementation here:

    int i = 0;
    int j = i;
    for(++i; i < s; ++i)
    {
        if (!(arr[j] == arr[i]) && !(++j == i)) {
            arr[j] = arr[i];
        }
    }
    ++j;
    cout<<"Your array after removing duplicacy now is"<<endl;
    for (int i=0;i<j;i++)
        {
            cout<<arr[i]<<" ";
        }
    return 0;

Additionally, there are further advanges to this:

  1. Linear time-complexity
  2. No restriction with regards to random-access / bidirectional iterator. Only forward iterators are required (of course, the current implementation makes direct use of random-access containers)
Arnab De0

To make your code more efficient you can use XOR(^) it will remove two same numbers with better time complexity.

Hąřïøm Ñąÿmā0
Related