Hi eveyone!
This is the first blog and the first problem that I wrote. I will share the problem and some different approaches to solve it. If you want to try it first, here is the statement:
There are $$$N$$$ children in a circle. During the game, every other child is removed from the circle until there are no children left (classic Josephus Problem). The order of removals creates a permutation of $$$N$$$ and lets call that $$$p$$$. I want you to find for all $$$i$$$ such that $$$1 \leq i \leq N$$$ and $$$p_i = i$$$. Print them in increasing order. If there is no such a number print $$$-1$$$. For example for $$$N = 7$$$ the permutation is $$$p = {2, 4, 6, 1, 5, 3, 7}$$$. 5th number is 5 and 7th number is 7 so you should print 5 7. There is also $$$T$$$ test cases.
$$$1 \leq T \leq 2 * 10^5$$$
$$$1 \leq N \leq 10^9$$$
I couldn't figure it out but then I've find a solution by looking the answer patterns. I still have no clue why it is like that but here is my code and explanation. I'm sure both solutions are correct, I've checked them with a slower time complexity bruteforce way.
Idea: olasiliksizci
There is another solution with different approach.
Idea: Leadd
There is a hard version of that problem which is I'm completely unsure if it has a solution or not. Only difference is instead of skipping 1 child, skip k child. For example $$$N = 7$$$, $$$K = 2$$$. $$$P = {3, 6, 2, 7, 5, 1, 4}$$$ the answer is 5.
Thanks for reading my very first blog, don't forget to comment and share your ideas.








You can find the solution to k >= 2 here ... Just read few days ago
Yes... But not I am asking for. The constraint on $$$N$$$ is up to $$$10^9$$$ so I can't find order for each element I guess. Also I don't want to create the permutation at all.
I think this article talks about the last remaining number and not how to get the order of removals.