CodingGyan

Josephus Survivor

medium Recursion and Backtracking

Problem

n people stand in a circle, numbered 1 to n. Starting from person 1, count k people (person 1 is the first) and remove the k-th. Start counting again from the next person. Repeat until one person is left. Print the number of the survivor. Input: n and k.

Constraints

  • 1 <= n <= 1000
  • 1 <= k <= 1000

Examples

Input

7 3

Output

4

Solutions

Best approachTime O(n)Space O(n)

After the first removal the circle has n - 1 people and the count restarts at the next person. So J(n) = (J(n - 1) + k) mod n with J(1) = 0. We add 1 at the end for 1-based numbers. O(n) time.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Josephus.
 * Input   : n and k.
 * Output  : Survivor number.
 * Approach: Recurrence.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        private static long survivor(long people, long k) {
            if (people == 1) {
                return 0;
            }
            return (survivor(people - 1, k) + k) % people;
        }

    // This method solves the task. It receives the input and returns the answer.
    static long solve(long a, long b) {
        // Step 1: With one person left, the survivor is at position 0 (we count from 0).
        // Step 2: With n people, one removal gives a circle of n - 1. Shift the smaller answer by k to get the answer for n.
        return survivor(a, b) + 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        System.out.println(solve(a, b));
    }
}
Hints (2)
  1. What is the answer for one person?
  2. Why do we add k and take mod n?