C++ Loop/Array Practice Problem – Josephus Problem

Time Limit: 2s Memory Limit: 192MB

Problem Description

There are n people standing in a circle, numbered sequentially. Starting from the first person, they count off (from 1 to 3), and anyone who counts to 3 is eliminated from the circle. The task is to determine the original number of the last person remaining.

Input Format

Initial number of people n

Output Format

The initial number of the last person remaining

Sample Input

3

Sample Output

2

Code

#include <iostream>
#include <vector>
using namespace std;

int josephus(int n) {
    vector<int> people(n);
    for (int i = 0; i < n; i++) {
        people[i] = i + 1; // Numbering from 1 to n
    }
    int index = 0; // Index of the current person counting
    while (people.size() > 1) {
        // Find the position of the person to be eliminated
        index = (index + 2) % people.size(); // Counting 1,2,3 corresponds to index + 2
        // Eliminate this person
        people.erase(people.begin() + index);
    }
    return people[0];
}

int main() {
    int n;
    cin >> n;
    cout << josephus(n) << endl;
    return 0;
}

Output ResultCode Explanation(1) josephus function: Creates a vector containing numbers from 1 to n Uses a loop to continuously eliminate the person counting to 3 until only one remains Each time calculates the position of the person to be eliminated: (current index + 2) % remaining people Uses the vector’s erase method to remove the eliminated person Returns the number of the last remaining person(2) Main function: Reads the number of people n Calls the josephus function to calculate the result Outputs the number of the last remaining personProcessing Steps:

1. Initial: [1, 2, 3]
2. Round 1: Count 1(1), 2(2), 3(3) → Eliminate 3 → Remaining [1, 2]
3. Round 2: Start counting from 1: Count 1(1), 2(2), 3(1) → Eliminate 1 → Remaining [2]
4. Last remaining is 2

Optimization NotesUsing vector to simulate a circular linked listMathematical method to calculate the elimination position, avoiding unnecessary traversalTime complexity O(n^2), efficient enough for small nOptimization NotesUsing vector to simulate a circular linked listMathematical method to calculate the elimination position, avoiding unnecessary traversalTime complexity O(n^2), efficient enough for small n

int josephus(int n) {
    if (n == 1) return 1;
    return (josephus(n - 1) + 2) % n + 1;
}

SuggestionsDiscuss the historical background of the Josephus problemCompare the efficiency of the simulation method and the mathematical methodDiscuss how to extend it to any counting limit kEncourage students to manually simulate small-scale cases

C++ Basic Tutorial Collection

C++ Basic Resources

1. C++ Output

2. C++ Variables

3. C++ Input

4. C++ Expressions

5. IF Statements

6. IF Applications

7. WHILE Loop Statements

8. FOR Loop Statements

9. Arrays

10. One-dimensional Arrays

11. Two-dimensional Arrays

12. C++ Functions

13. C++ File Operations – Writing Files

If you find it interesting, just click on me