Loading...
Loading...
Loading...
After a cricket match, n friends sit in a circle, numbered 1 to n clockwise. They use a counting game to choose who does not pay for the cab ride.
Starting from friend 1, they count clockwise 1, 2, ..., k. The friend who says k leaves the circle. Counting starts again at 1 from the next friend still in the circle.
This repeats until one friend is left. Print the number of that friend.
Example 1
Input
5 2
Output
3
Friends leave in the order 2, 4, 1, 5. Friend 3 is left.
Example 2
Input
7 3
Output
4
Friends leave in the order 3, 6, 2, 7, 5, 1. Friend 4 is left.
Try the problem first. Open one hint at a time.
Number the friends from 0 instead of 1 while you think, and add 1 only when you print.
After the first friend leaves, the counting restarts with n - 1 friends. That is the same game, just smaller and shifted.
If friend s (counting from 0) is left in the smaller game, the same person sits k places further round in the bigger circle: (s + k) mod n.
With one friend, the survivor is friend 0. Build up from there with a method that calls itself on n - 1.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor