224. The Josephus Problem

Challenge1000 ms256 MBSolved by 0%

n people stand in a circle, numbered 1 to n. Counting starts at person 1, and every kth person is removed. Counting then continues from the next person, around and around, until one is left.

Print the number of the survivor.

Simulating the circle works and costs n removals from a list, which at a million people is far too slow if each removal shifts everything after it.

The recursive insight is much better. After the first removal you have the same problem with n-1 people, and the only difference is where the numbering starts.

Constraints - `1 ≤ n ≤ 1000000` - `1 ≤ k ≤ 1000000`

Input

A single line containing two integers n and k.

Output

Print one integer, the position of the survivor, numbered from 1.

Input5 2

Output3

Noteis small enough to work through on paper

Input1 1

Output1

Noteis one person, who survives by default

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution