In my approach, I first take all the values from 1 to n in a vector. Then,print (pos+k)th value from vector and then erase the pos .Here, the erase function creates extra time complexity as vector erase costs O(n) times.

Now,please help me with that. Thank you.

My code-(I)

signed main()
{
int n,k;cin>>n;
vector<int>josep;
for(int i=1;i<=n;++i)josep.push_back(i);
int pos=0;
while((int)josep.size()>1)
{
pos=(pos+1)%(int)josep.size();
cout<<josep[pos]<<' ';
josep.erase(josep.begin()+pos);
pos%=(int)josep.size();
}
cout<<josep.at(0)<<' ';
cout<<endl;
return 0;
}

My code-(II)

signed main()
{
int n,k;cin>>n>>k;
vector<int>josep;
for(int i=1;i<=n;++i)josep.push_back(i);
int pos=0;
while((int)josep.size()>1)
{
pos=(pos+k)%(int)josep.size();
cout<<josep[pos]<<' ';
auto it=find(josep.begin(),josep.end(),josep[pos]);
josep.erase(it);
pos%=(int)josep.size();
}
cout<<josep.at(0)<<' ';
cout<<endl;
return 0;
}

You can use always use ordered sets instead of vectors to simulate the process (as it has an O(logN) erase and insert time), but itâ€™d be interesting to know if there exists a more clever solution to this, instead of just blindly simulating the process.

AC_CODE FOR JOSEPHUS-2

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
signed main(){
int n,k;
cin >> n >> k;
int p =k%n ; oset<int>a ;
for(int i=1;i<=n;i++)
a.insert(i) ;
while(a.size()){
int r = *a.find_by_order(p) ;
a.erase(r) ;
if(a.size())
p=(p+k)%a.size() ;
cout << r << " " ;
}
}

Oh, I have made a blunder. I havenâ€™t looked at the sample input and output. I should have noted carefully. Itâ€™s my fault. Anyways, I guess the problem 1 can be solved using Circular Linked Lists, I guess.

Just donâ€™t write your random thoughtsâ€¦ Look now after deletion of even numbers odd numbers will be deleted alternatelyâ€¦ Please delete your comment

you can always use queue . add 1 to n elements in a queue. just pop the first element and add it to the queue again. Now the second element, or now the first element in the queue, push it in the vector and pop. continue till you have 1 element left in the queue. Also push the last element, print the vector