CSES Solutions - Josephus Problem II

Consider a game where there are N children (numbered 1,2 ... N) in a circle. During the game, repeatedly K children are skipped and one child is removed from the circle. In which order will the children be removed?

Examples:

Input: N = 7, K = 2
Output: 3 6 2 7 5 1 4
Explanation:

• children = [1, 2, 3, 4, 5, 6, 7], 1 and 2 are skipped and 3 is removed.
• children = [1, 2, 4, 5, 6, 7], 4 and 5 are skipped and 6 is removed.
• children = [1, 2, 4, 5, 7], 7 and 1 are skipped and 2 is removed.
• children = [1, 4, 5, 7], 4 and 5 are skipped and 7 is removed.
• children = [1, 4, 5], 1 and 4 are skipped and 5 is removed.
• children = [1, 4], 1 and 4 are skipped and 1 is removed.
• children = [4], 4 is skipped and removed.

Input: N = 6, K = 1
Output: 2 4 6 3 1 5
Explanation:

• children = [1, 2, 3, 4, 5, 6], 1 is skipped and 2 is removed.
• children = [1, 3, 4, 5, 6], 3 is skipped and 4 is removed.
• children = [1, 3, 5, 6], 5 is skipped and 6 is removed.
• children = [1, 3, 5], 1 is skipped and 3 is removed.
• children = [1, 5], 5 is skipped and 1 is removed.
• children = [5], 5 is skipped and removed.

Approach: To solve the problem, follow the below idea:

We can solve this problem by storing the numbers in a 2D vector of which size of each inner vector is int(sqrt(N)). We will arrange all the children in rows and columns such that each row has at max sqrt(N) columns. Now, we can start from the first row and move to the next rows by making jumps of size sqrt(N) while finding the Kth child to remove. After removing the Kth child, we can again move to the next row making jumps of size sqrt(N). We can take two indices to keep track of the row and column. As soon as we reach the child to be removed, we mark the child as removed and resize the array. Also, if we exceed all the rows we start from the first row again.

Step-by-step algorithm:

• Maintain a 2D array arr[][] which has at max sqrt(N) elements in each row.
• Initialize row = 0 and column = 0.
• Iterate a loop from 0 to N - 1 to keep track of the children removed.
  • Find the position of the element to be removed.
  • Move to the element to be removed by making jumps of size sqrt(N).
  • After reaching the element to be removed, remove the element and resize the row.
  • Also keep track of the row and column such that the row does not exceed the total number of rows in arr[][] and cols does not exceed the number of elements present in the row.
• After N removals, all children are printed in order.

Below is the implementation of the algorithm:

#include <bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000007 // Function to print the order in which children are removed void solve(int N, int K) {  // 2D array to store ranges of size sqrt(N)  vector<vector<int> > arr;  int root = sqrt(N);  int row = 0, col = 0, count = 0;  // Construct the 2D vector arr  vector<int> vec;  for (int i = 1; i <= N; i++) {  if (count > root) {  count = 0;  arr.push_back(vec);  vec.clear();  }  vec.push_back(i);  count++;  }  if (!vec.empty())  arr.push_back(vec);  // Iterate till we have removed all the children  for (int i = 0; i < N; i++) {  // Fnd the position of the element to be removed  int j = K % (N - i);  // Make jumps till we reach the position of the  // element to be removed  while (j) {  // If we can jump j elements in the current row,  // we jump to that column  if (col + j < arr[row].size()) {  col += j;  j = 0;  }  // If we cannot jump j elements, we jump over  // all the elements in the current row and move  // to the next row  else {  j -= arr[row].size() - col;  col = 0;  row++;  }  // If all the elements are traversed, we start  // from the first row again  if (row >= arr.size())  row = 0;  }  // While the current row has lesser columns, move to  // the next row  while (arr[row].size() <= col) {  col = 0;  row++;  if (row >= arr.size())  row = 0;  }  cout << arr[row][col] << " ";  if (i != N - 1) {  // Remove the student from the current row  arr[row].erase(arr[row].begin() + col);  while (arr[row].size() <= col) {  col = 0;  row++;  if (row >= arr.size())  row = 0;  }  }  } } int main() {  // Sample Input  int N = 6, K = 1;  solve(N, K);  return 0; } 

import java.util.ArrayList; public class RemoveChildrenOrder {  public static void solve(int N, int K) {  // 2D array to store ranges of size sqrt(N)  ArrayList<ArrayList<Integer>> arr = new ArrayList<>();  int root = (int) Math.sqrt(N);  int row = 0, col = 0, count = 0;  // Construct the 2D vector arr  ArrayList<Integer> vec = new ArrayList<>();  for (int i = 1; i <= N; i++) {  if (count > root) {  count = 0;  arr.add(new ArrayList<>(vec));  vec.clear();  }  vec.add(i);  count++;  }  if (!vec.isEmpty())  arr.add(new ArrayList<>(vec));  // Iterate till we have removed all the children  for (int i = 0; i < N; i++) {  // Find the position of the element to be removed  int j = K % (N - i);  // Make jumps till we reach the position of the  // element to be removed  while (j > 0) {  // If we can jump j elements in the current row,  // we jump to that column  if (col + j < arr.get(row).size()) {  col += j;  j = 0;  }  // If we cannot jump j elements, we jump over  // all the elements in the current row and move  // to the next row  else {  j -= arr.get(row).size() - col;  col = 0;  row++;  }  // If all the elements are traversed, we start  // from the first row again  if (row >= arr.size())  row = 0;  }  // While the current row has fewer columns, move to  // the next row  while (arr.get(row).size() <= col) {  col = 0;  row++;  if (row >= arr.size())  row = 0;  }  System.out.print(arr.get(row).get(col) + " ");  if (i != N - 1) {  // Remove the student from the current row  arr.get(row).remove(col);  while (arr.get(row).size() <= col) {  col = 0;  row++;  if (row >= arr.size())  row = 0;  }  }  }  }  public static void main(String[] args) {  // Sample Input  int N = 6, K = 1;  solve(N, K);  } } // This code is contributed by rambabuguphka 

using System; using System.Collections.Generic; public class ChildrenOrder {  // Function to print the order in which children are removed  public static void Solve(int N, int K)  {  // 2D list to store ranges of size sqrt(N)  List<List<int>> arr = new List<List<int>>();  int root = (int)Math.Sqrt(N);  int row = 0;  int col = 0;  int count = 0;  // Construct the 2D list arr  List<int> vec = new List<int>();  for (int i = 1; i <= N; i++)  {  if (count > root)  {  count = 0;  arr.Add(vec);  vec = new List<int>();  }  vec.Add(i);  count++;  }  if (vec.Count > 0)  {  arr.Add(vec);  }  // Iterate till we have removed all the children  for (int i = 0; i < N; i++)  {  // Find the position of the element to be removed  int j = K % (N - i);  // Make jumps till we reach the position of the element to be removed  while (j > 0)  {  // If we can jump j elements in the current row, we jump to that column  if (col + j < arr[row].Count)  {  col += j;  j = 0;  }  // If we cannot jump j elements, we jump over all the elements in the current row and move to the next row  else  {  j -= arr[row].Count - col;  col = 0;  row++;  if (row >= arr.Count)  {  row = 0;  }  }  }  // While the current row has lesser columns, move to the next row  while (arr[row].Count <= col)  {  col = 0;  row++;  if (row >= arr.Count)  {  row = 0;  }  }  Console.Write(arr[row][col] + " ");  if (i != N - 1)  {  // Remove the student from the current row  arr[row].RemoveAt(col);  while (arr[row].Count <= col)  {  col = 0;  row++;  if (row >= arr.Count)  {  row = 0;  }  }  }  }  Console.WriteLine();  }  public static void Main(string[] args)  {  // Sample Input  int N = 6;  int K = 1;  Solve(N, K);  } } 

// Function to print the order in which children are removed function solve(N, K) {  // 2D array to store ranges of size sqrt(N)  let arr = [];  let root = Math.sqrt(N);  let row = 0, col = 0, count = 0;  // Construct the 2D array arr  let vec = [];  for (let i = 1; i <= N; i++) {  if (count > root) {  count = 0;  arr.push([...vec]);  vec = [];  }  vec.push(i);  count++;  }  if (vec.length !== 0)  arr.push([...vec]);  // Iterate till we have removed all the children  for (let i = 0; i < N; i++) {  // Find the position of the element to be removed  let j = K % (N - i);  // Make jumps till we reach the position of the element to be removed  while (j) {  // If we can jump j elements in the current row, we jump to that column  if (col + j < arr[row].length) {  col += j;  j = 0;  }  // If we cannot jump j elements, we jump over all the elements in the current row and move to the next row  else {  j -= arr[row].length - col;  col = 0;  row++;  }  // If all the elements are traversed, we start from the first row again  if (row >= arr.length)  row = 0;  }  // While the current row has fewer columns, move to the next row  while (arr[row].length <= col) {  col = 0;  row++;  if (row >= arr.length)  row = 0;  }  process.stdout.write(`${arr[row][col]} `);  if (i !== N - 1) {  // Remove the student from the current row  arr[row].splice(col, 1);  while (arr[row].length <= col) {  col = 0;  row++;  if (row >= arr.length)  row = 0;  }  }  } } // Sample Input const N = 6, K = 1; solve(N, K); 

import math # Function to print the order in which children are removed def solve(N, K): # 2D list to store ranges of size sqrt(N) arr = [] root = int(math.sqrt(N)) row = 0 col = 0 count = 0 # Construct the 2D list arr vec = [] for i in range(1, N + 1): if count > root: count = 0 arr.append(vec) vec = [] vec.append(i) count += 1 if vec: arr.append(vec) # Iterate till we have removed all the children for i in range(N): # Find the position of the element to be removed j = K % (N - i) # Make jumps till we reach the position of the element to be removed while j: # If we can jump j elements in the current row, we jump to that column if col + j < len(arr[row]): col += j j = 0 # If we cannot jump j elements, we jump over all the elements in the current row and move to the next row else: j -= len(arr[row]) - col col = 0 row += 1 if row >= len(arr): row = 0 # While the current row has lesser columns, move to the next row while len(arr[row]) <= col: col = 0 row += 1 if row >= len(arr): row = 0 print(arr[row][col], end=" ") if i != N - 1: # Remove the student from the current row del arr[row][col] while len(arr[row]) <= col: col = 0 row += 1 if row >= len(arr): row = 0 print() # Sample Input N = 6 K = 1 solve(N, K) 

2 4 6 3 1 5 

Time Complexity: O(N * sqrt(N)), where N is the number of children.
Auxiliary Space: O(N)