How to solve Josephus Queries (CSES)?

Consider a game where there are n children (numbered 1,2,…,n) in a circle. During the game, every second child is removed from the circle, until there are no children left.

Your task is to process q queries of the form: “when there are n children, who is the kth child that will be removed?”


Did you find the solution?
I used recursion to solve the first was:-
J(n,k) = (J(n-1,k-1)+2)%n,
J(1,k) = 0,
J(n,1) = 1
The answer is J(n,k) +1 because we have indexed the children in circle from 0.
Second subtask times out with recursion. Is there any mathematical formula?

I’ll give you a hint. You can still use recursion.
Code: #include <bits/stdc++.h>using namespace std; int get(int n,int k,int first -

1 Like