forked from TheAlgorithms/C-Sharp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
JosephusProblem.cs
33 lines (28 loc) · 968 Bytes
/
JosephusProblem.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using System;
namespace Algorithms.Numeric;
public static class JosephusProblem
{
/// <summary>
/// Calculates the winner in the Josephus problem.
/// </summary>
/// <param name="n">The number of people in the initial circle.</param>
/// <param name="k">The count of each step. k-1 people are skipped and the k-th is executed.</param>
/// <returns>The 1-indexed position where the player must choose in order to win the game.</returns>
public static long FindWinner(long n, long k)
{
if (k <= 0)
{
throw new ArgumentException("The step cannot be smaller than 1");
}
if (k > n)
{
throw new ArgumentException("The step cannot be greater than the size of the group");
}
long winner = 0;
for (long stepIndex = 1; stepIndex <= n; ++stepIndex)
{
winner = (winner + k) % stepIndex;
}
return winner + 1;
}
}