Josephus Problem - Find the Winner

N people numbered 1 to N stand in a circle. Starting the count at person 1 and counting in a fixed direction, every K-th person is eliminated from the circle, and counting then continues from the next remaining person. This repeats until only one person remains. Using recursion on the classic Josephus recurrence, determine the number (1 to N) of the last person remaining.

Input: A single line containing two space-separated integers N and K. Output: A single line containing the 1-based position of the last remaining person.

1 <= N <= 5000, 1 <= K <= 5000.

Converting between 0-indexed (used internally by the clean recurrence) and 1-indexed (used for the final answer) is a small but essential detail - forgetting this conversion is the single most common bug when implementing the Josephus problem.

People stand in a circle, and every K-th person is eliminated repeatedly until one remains - find that survivor, using a recursive formula. Brute force: Simulate the entire elimination process directly using a data structure like a circular linked list, physically removing every K-th person - this works and is intuitive, but costs O(n*K) or worse, less elegant than the direct recurrence. Optimised: The Josephus recurrence J(n) = (J(n-1)+K) % n captures a beautiful mathematical relationship: the survivor's position when starting with n people can be derived directly from the survivor's position with n-1 people, WITHOUT ever simulating a single elimination - building this up from J(1)=0 to J(N) takes just O(N) simple arithmetic steps.

1. Solve the 0-INDEXED version first: J(1) = 0 (with just one person, they trivially survive at position 0). 2. The RECURRENCE: J(n) = (J(n-1) + K) % n for n > 1 - the survivor's position in a circle of size n relates directly to the survivor's position in a circle of size n-1. 3. Convert the final 0-indexed answer back to 1-INDEXED by adding 1 before printing.

Time: O(N) - building up the recurrence from J(1) to J(N), one simple calculation per step. Space: O(1) if computed iteratively (bottom-up), or O(N) recursion stack if computed top-down recursively.

N = 1 always outputs 1 (only one person, nobody is ever eliminated). K = 1 eliminates people in simple increasing order, leaving the person originally at position N.

Be ready to explain WHY the recurrence works - it's a genuinely non-obvious mathematical result, and being able to at least sketch the intuition (rather than just applying a memorized formula) is what separates surface familiarity from real understanding.