So a general bit of advice for this problem is that the solution I have in mind is not trivial at all—it involves plenty of cleverness to come up with and some careful accounting of all of the edge cases to prove that it works. My solution is most likely not the simplest possible but my suspicion is that no solution is going to be as simple as the ones people have proposed thus far.
If you think you have a simple solution, your solution is probably wrong.
So a general bit of advice for this problem is that the solution I have in mind is not trivial at all—it involves plenty of cleverness to come up with and some careful accounting of all of the edge cases to prove that it works. My solution is most likely not the simplest possible but my suspicion is that no solution is going to be as simple as the ones people have proposed thus far.
If you think you have a simple solution, your solution is probably wrong.