What's wrong in my approach in a problem of game of death in a circle?

Question

#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
using namespace std;
void safe(int n,int k,int a[])
{
    vector<int>s(a+0,a+n);
    vector<int>b(a+0,a+n);
    while(s.size()>1)
    {
        int r;
        r=s.size();
       int count=1;
        while(count<=r)
        {
            b[count%r]=0;
            count=count+k;
        }
    b.erase(remove(b.begin(),b.end(),0),b.end());
    s=b;    
    }
    
    for(int x:s)
    {
        cout<<x<<"\n";
    }
}


int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int n,k;
        cin>>n>>k;
        int *a=new int[n];
        for(int j=1;j<=n;j++)
        {
            a[j-1]=j;
        }
        if(n>2)
        {
        safe(n,k,a);
        }
        else if(n==2)
        {
     cout<<a[1]<<"\n";
        }
        else
        cout<<a[0]<<"\n";
    }
}

Input:

Output:

1
3
2
19  --> it should be 36

If you don't know this problem Description of question: There are n people standing in a circle (numbered clockwise 1 to n) waiting to be executed. The counting begins at point 1 in the circle and proceeds around the circle in a fixed direction (clockwise). In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. Consider if n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1 is killed. Finally, the person at position 5 is killed. So the person at position 3 survives.

Wrong output on giving 50 10 as input ,i must get 36 ,but it's giving 19.I scratched my head for long but couldn't get it that what's wrong,can you see? — Mayank tiwari, Dec 03 '20 at 19:30
`int *a=new int[n];` -- Why are you doing this when you could have simply used `std::vector a(n);`? Right now, that loop leaks memory. — PaulMcKenzie, Dec 03 '20 at 20:12
I think goes wrong right from the start because it always kills the first person, I believe it should kill the kth person. — Peter Hull, Dec 03 '20 at 20:23
And it also slows downs your build time s by close to an an order of magnitude because it includes the entire freaking C++ Standard Library. That's a load of code that needs to be loaded from disk and compiled just so you can get a few extra identifiers. It's not worth using. The time saved typing fewer includes is eaten up by at most two compiles. — user4581301, Dec 03 '20 at 20:43
One thing wrong is that you are using `#include ` which is not a standard header file. — Thomas Matthews, Dec 03 '20 at 23:37
The `using namespace std;` should be avoided. List the items individually to avoid bringing in *all* the symbols in `std`. Example: `using std::cout;` — Thomas Matthews, Dec 03 '20 at 23:38
Not using namespace std ,like seriously I have to type std again and again,if it has any advantage? — Mayank tiwari, Dec 04 '20 at 05:18
@Mayanktiwari Yes, it's definitely worth the effort of saying `std::` everywhere. Please read this https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice — cigien, Dec 04 '20 at 14:33

score 1 · Accepted Answer · answered Dec 03 '20 at 20:55

Here is a possible solution, hopefully the comments make it clear. There's no need to allocate an int[] and copy it into the vector, you can init the vector directly with iota. Likewise you can remove elements as you go, rather than zeroing and removing as a later step.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;
void safe(int n, int k) {
  vector<int> s(n);
  // Init the vector 1..n
  iota(s.begin(), s.end(), 1);
  int i = 0;
  // While more than one survive...
  while (s.size() > 1) {
    // Skip forward (k-1)
    i = (i + k - 1) % s.size();
    // Kill the next one
    s.erase(s.begin() + i);
  }
  for (int x : s) {
    cout << x << "\n";
  }
}

int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    int n, k;
    cin >> n >> k;
    if (n > 2) {
      safe(n, k);
    } else if (n == 2) {
      cout << 2 << "\n";
    } else
      cout << 1 << "\n";
  }
}

What's wrong in my approach in a problem of game of death in a circle?

1 Answers1