Given an array a[] of size N which contains elements from 0 to N-1, you need to find all the element-CodePudding

Given an array a[] of size N which contains elements from 0 to N-1, you need to find all the elements occurring more than once in the given array. Input: N = 4 a[] = {0,3,1,2} Output: -1 Explanation: N=4 and all elements from 0 to (N-1 = 3) are present in the given array. Therefore output is -1.

What is wrong with the following solution?

vector<int> duplicates(int arr[], int n) {
        unordered_set<int> m;
        vector<int> ans;
        for(int i=0;i<n;i  ){
            //if element is found
            if(m.find(arr[i])!=m.end())
                ans.push_back(arr[i]);
            //if element is not found
            else
                m.insert(arr[i]);
    }
    if(ans.empty())
        ans.push_back(-1);
    return ans;
}

CodePudding user response：

This solution returns values more than once if they appear more than twice.

For example, for a = {1, 1, 1}, it will return {1, 1}, when the correct answer is just {1}.

CodePudding user response：

The solution has one problem. For each value, that is already in the set, you will add the value to the result. If there are more than 2 identical values, than you will always add the same value again to the resulting vector.

Let us look at the following example: {1,2,3,42,42,42,42}:

Loop 
run   value  set         vector
 0      1     1            -
 1      2     1,2          -
 2      3     1,2,3        -
 3      42    1,2,3,42     -
 4      42    1,2,3,42     42         Duplicate found. Add to vector   
 5      42    1,2,3,42     42,42      Again duplicate found. Add again to vector 
 6      42    1,2,3,42     42,42,42   Again duplicate found. Add again to vector

So, this solution will unfortunately not work.

What you need to do instead is to find out, if a value is present more than one time. And this you can to by counting values and then check, if the count is more than one and then add the value to the resulting std::vector

The standard approach for counting is to use a std::unordered_map, where we can associate a count with each value.

So, first we will count all values. Then, we will evaluate the counters and add all values to the resulting vector, if the count is greater than 1.

A potential solution could look like this:

#include <iostream>
#include <vector>
#include <unordered_map>

std::vector<int> duplicates(int arr[], int n) {

    // Here we will count the occurence of each integer in the array
    std::unordered_map<int, unsigned int> counter{};

    // Do the counting
    for (int i = 0; i < n;   i)
        counter[arr[i]]  ;
    
    // This will hold the result. Either the duplicates, or -1 of no duplicate
    std::vector<int> result{};

    // Check all counted values. If the counter is more than one for a vakue, add it (only one time to the result)
    for (const auto& [value, count] : counter)
        if (count > 1) result.push_back(value);

    // If there was no duplicate, then add -1 to the vector
    if (result.empty()) result.push_back(-1);

    return result;
}
int main() {
    int arr[]{ 0,1,2,3,42,42,42};
    for (int i : duplicates(arr, sizeof(arr) / sizeof(arr[0])))
        std::cout << i << ' ';
}

I will show the original solution with comments. And by reading the comments, you will understand the problem.

I would recommend to you, to write as many comments as posible. Then, you will detetct problems by yourself in an early phase.

#include <vector>
#include <iostream>
#include <unordered_set>

using namespace std;

vector<int> duplicates(int arr[], int n) {

    // This set can contain only unique values
    unordered_set<int> m;

    // Here we will store the result
    vector<int> ans;

    // Iterate over all values in the array
    for (int i = 0; i < n; i  ) {

        // Check, if the value from the array is already in the set
        if (m.find(arr[i]) != m.end())

            // Yes it is alread in the set
            // So add it to the resulting answer
            // **** But caveat: If there are 5 identical duplicates, 
            // we will add 4 times the value to the answer --> Bug
            ans.push_back(arr[i]);
        else
            // If element is not found, so, was not yet present in the set, add it
            m.insert(arr[i]);
    }
    // Special case for no duplicates
    if (ans.empty())
        ans.push_back(-1);
    return ans;
}
int main() {
    int arr[]  {0,1,2,3,42,42,42,42,42};
    for (int i : duplicates(arr, sizeof(arr)/sizeof(arr[0])))
        cout << i << ' ';
}

CodePudding user response：

Gassa correctly identified a bug. The fix is to do it in two iterations instead of trying to do it in one iteration of the array.

Here's a simple way to do it without set. Take advantage of the fact that all the elements in the array will be between 0..N-1 by using another vector.

vector<int> duplicates(int arr[], int n) {

    vector<int> table;     // tracks number of occurrences of a value in arr
    vector<int> duplicates;

    table.resize(n);
    for (int i = 0; i < n; i  )
    {
       table[arr[i]]  ;
    }

    for (int i = 0; i < n; i  )
    {
       if (table[i] > 1)
       {
          duplicates.push_back(i);
       }
    }
    if (duplicates.size() == 0)
    {
       duplicates.push_back(-1);
    }
    return duplicates;
}