Solution to Last Number In Circle from Jobdu

11 Sep

Question (in Chinese):

Question Name: Last Number In Circle

Question Description: N persons are standing in a circle. We are removing the one from the circle every M persons, until only one person is in its original position. Find out the last person.

Input: the input might contain multiple test cases. One single line is a test case. Each line may contain one or two integers. If it contain one integer 0, we are exiting the program. If the line include two integers N (0 <= N <= 1000000) and M (1 <= M <= 1000000). N is the number of persons. And persons are numbers from 1. M is the interval.

Output: print the ID number of the last person in the circle.

This question is the Josephus problem. The solution is:

Leave a Reply

Your email address will not be published. Required fields are marked *