Output is not what expect

Question

Here is a question from codewars.com

Given a list and a number N, create a new list that contains each number of lst at most N times without reordering. For example if N = 2, and the input is [1,2,3,1,2,1,2,3], you take [1,2,3,1,2], drop the next [1,2] since this would lead to 1 and 2 being in the result 3 times, and then take 3, which leads to [1,2,3,1,2,3].

And here is my code:

std::vector<int> deleteNth(std::vector<int> arr, int n)
{
   int counting = 0;
   int counting2 = 0;
   for (int i : arr)
   {
    for (int j : arr)
    {
     cout << arr.size() << "  " << counting<<"  "<<counting2<<endl;
        if (i == j) 
        {
            ++counting;
            if (counting > n) { arr.erase(arr.begin() + counting2); --counting2; }
        }

        counting2++;
    }
    counting = 0;
    counting2 = 0;
}
return arr;

The basic tests are fine. But when i attemp their random test. It 's a mess.

Expected: equal to [ 8, 32, 32, 8, 8, 26, 26, 8, 19, 26, 26, 19, 26, 26, 19, 8, 8, 19, 26, 8, 8, 19, 32, 32, 26, 50, 19, 32, 32, 32, 19] Actual: [ 8, 32, 32, 8, 8, 26, 26, 8, 19, 26, 26, 19, 26, 26, 19, 8, 8, 19, 26, 8, 8, 19, 32, 26, 50, 19, 32, 32, 19 ]

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5910058) — Jesper Juhl, Apr 19 '20 at 15:32
Hi! Look, nobody can look at it once and say "ah, yes, you forgot to schmurgle the pfrumpf in your haggawoolishing function", what we'd have to do is load it in a debugger, step through it, see where it derivates from the expected path, and so on. This comes at additional overhead especially because we don't have _your_ knowledge as author of the code. It would be helpful if you could start by debugging your code yourself. Google `how to debug c++` plus your compiler to find info about it. Or try [this online tool](https://www.onlinegdb.com/online_c++_compiler) which comes with a tutorial too. — CherryDT, Apr 19 '20 at 15:33
Calling `.erase` inside the loop is UB. Just create a new vector instead. — cigien, Apr 19 '20 at 15:34

score 0 · Accepted Answer · answered Apr 19 '20 at 15:38

I see that you have two nested loops here. You can acheive what you want to do with a single loop. Just use a frequency array. Here I'm using std::map because the range of numbers in unknown. If the range is known, you can use an array or std::vector and have the code run in O(N).

#include <iostream>
#include <vector>
#include <map>

std::vector<int> deleteNth(std::vector<int>& arr, int n)
{
    std::map<int, int> freq;
    std::vector<int> result;

    for (int number : arr)
    {
        if (freq[number] >= n)
            continue;

        result.push_back(number);
        freq[number]++;
    }

    return result;
}

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

    for (int i : result)
        std::cout << i << ' ';
}

Output:

1 2 3 1 2 3

Output is not what expect

1 Answers1