I'm revisiting CSES problem set to help a friend. In "Sorting and Searching", there is this problem: Josephus Problem II. My solution was using an ordered set, and after a quick search, it seems like everyone online did this too. However, we see the more general version of this problem: List Removals in the section "Range Queries".
The category of this problem and a solution which is more general made me wonder if there is an alternative solution, perhaps without ordered set. I did some search online and found O(n) solution to the Josephus Problem (also see cp-algorithm). But this is different from the CSES problem, as it only finds the last element.
So, out of curiosity, is there any solution that is not doing removal on ordered set? Otherwise, this feels like a pretty bad problem.
There is a way to solve this by partitioning the removed array (where removed[i] is true if the ith element has been removed) into ceil(N / L) length L segments and doing searches on these segments. The time complexity becomes O(N * max(ceil(N / L), L)), so if we set L = sqrt(N), becomes O(N * sqrt(N)).
This is definitely slower (and probably doesn't pass in other languages other than C++), but was the only solution that I could come up with that didn't require fancy data structures.
I solve this problem in O(N * sqrt(N)) by storing the numbers in a 2D vector of which size of each inner vector is int(sqrt(N)). So that the time complexity of both, finding the next number and erasing it can be O(sqrt(N)).
The code is here.