What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Math & Geometry

Builds on Linear DP, which you haven’t finished yet.

P3MediumMental model~3 min speedrun

Josephus Problem (Circular Elimination Recurrence)

Find the Winner of the Circular Game (LC 1823)(opens leetcode.com)

n friends sit around a circle, labeled 1 through n going clockwise, so stepping clockwise past friend n wraps you straight back to friend 1.

Play unfolds like this:

Everyone begins with friend 1 as the current spot.
From there, tick off k friends moving clockwise, counting the current friend as the first tick -- looping around the circle again if k is larger than however many friends remain.
Whichever friend the k-th tick lands on is eliminated and steps out of the circle.
As long as two or more friends remain, the next round starts its count from the friend standing immediately clockwise of the one who just left.
Once only one friend is left, that friend is declared the winner.

Given n and k, work out which friend wins.

Example 1

Input:n = 5, k = 2

Output:3

Tracking each round: (1) counting 1,2 from friend 1 eliminates 2, next count starts at 3; (2) counting 3,4 eliminates 4, next count starts at 5; (3) counting 5,1 eliminates 1, next count starts at 3; (4) counting 3,5 eliminates 5, leaving only friend 3, so friend 3 wins.

Josephus Problem

circle of n friends ➔ smaller circle's winner ➔ shift by k

Spot it when: People (or items) stand in a circle and every k-th one is removed until one is left; find who remains without simulating every removal.

Josephus Problem

Python

1	def find_the_winner(n: int, k: int) -> int:
2	"""Find the Winner of the Circular Game (Josephus): f(size) = (f(size - 1) + k) % size.
3	Time: O(N) \| Space: O(1)
4	"""
5	winner = 0 # 0-indexed winner of the game with 1 friend
6	for size in range(2, n + 1):
7	winner = (winner + k) % size # Shift the smaller game's winner k seats
8	return winner + 1 # Friends are numbered from 1

Invariant: winner is always the 0-indexed seat of the winner of the game with size friends.

Once the first friend leaves, the rest is the same game with one friend fewer, only started k seats later, so if winner is the answer for size - 1 friends, (winner + k) % size is the answer for size friends, and a loop from size = 2 up to n builds it without simulating anyone leaving. It is correct because removing the k-th friend and restarting from the next seat is exactly a shift of the smaller circle by k seats, and % size wraps that shift around the larger circle. The trap is the index base: the rule counts seats from 0, so start from winner = 0 for one friend and add 1 only in the final return, because the friends are numbered from 1.

See it run

Find the Winner of the Circular Game with n = 5 and k = 2

size 1winner 0

Each column is one circle size. The top row lists its seats, and the bottom row is the winner's seat for that size.

prev the winner's seat in the smaller circle
new the winner's seat in this circle

With 1 friend in the circle, the only seat is seat 0. So winner = 0.

seats

0 to 0

0 to 1

0 to 2

0 to 3

0 to 4

winner seat

0new

1 / 8

Gotchas1 of 4

The trap
Gotcha 1: Returning winner without adding 1
Mistake
```
return winner
```
Fix
```
return winner + 1
```
What happens: The recurrence counts seats from 0. So winner = 0 is the only seat when one friend is left. Find the Winner of the Circular Game (LC 1823) numbers the friends from 1. Only the final return adds 1.
Example: n = 5, k = 2
Mistake: returns 2Fix: returns 3
Gotcha 2: Wrapping with % n instead of % size
Mistake
```
winner = (winner + k) % n
```
Fix
```
winner = (winner + k) % size
```
What happens: At each step, the circle has size friends, not n. The shift of k seats happens in that smaller circle, so the wrap must use % size. With % n, winner can point past the last seat of the current circle.
Example: n = 5, k = 2
Mistake: returns 4Fix: returns 3
Gotcha 3: Simulating the circle with list.pop
Mistake
```
people = list(range(1, n + 1))
i = 0
while len(people) > 1:
    i = (i + k - 1) % len(people)
    people.pop(i)
return people[0]
```
Fix
```
winner = 0
for size in range(2, n + 1):
    winner = (winner + k) % size
return winner + 1
```
What happens: The simulation gives the same answer, and it passes the limits of Find the Winner of the Circular Game (LC 1823). Each pop(i) shifts the later friends, so the simulation takes O(N^2) time and O(N) space. The recurrence takes O(N) time and O(1) space.
Gotcha 4: Looping range(2, n) instead of range(2, n + 1)
Mistake
```
for size in range(2, n):
```
Fix
```
for size in range(2, n + 1):
```
What happens: range stops before its end value. So range(2, n) stops at a circle of n - 1 friends. It returns the winner of that smaller game.
Example: n = 5, k = 2
Mistake: returns 1Fix: returns 3

Not this one if…

Players pass a ball up to 10^10 times, but nobody leaves and each pass goes to a fixed receiver[i], as in Maximize Value of Function in a Ball Passing Game (LC 2836): the step is not k seats in a shrinking circle, so jump ahead by powers of two instead. See Binary Lifting

Deep Dive

Why one removal turns the game into a smaller game

Number the seats of a circle with size friends from 0 to size - 1. The count starts at seat 0 and goes k friends forward, so the friend at seat (k - 1) % size leaves. The next count starts at the friend after that seat, which is seat k % size.

The circle now has size - 1 friends, and the count starts at seat k % size. Relabel the friends so the one who starts the count is seat 0, and the others follow in circle order. This is exactly a new game with size - 1 friends that starts at seat 0.

Take n = 5 and k = 2. Friend 2 leaves first, so the five friends become the circle 3, 4, 5, 1, and the count starts at friend 3. Friend 3 is the new seat 0, and friend 3 is seat 2 in the original circle. The seat in the old circle is the seat in the new circle plus k, wrapped by the old size. That rule is (winner + k) % size.

Building the answer from one friend upward

With 1 friend, the winner is seat 0. So the loop starts with winner = 0 and applies winner = (winner + k) % size for size = 2, 3, ..., n. After the last pass, winner is the seat of the winner in the full circle.

For n = 5 and k = 2, the seats are 0, 0, 2, 0, 2 for sizes 1 to 5. The final seat is 2, and the friend number is 3. A direct simulation removes friends 2, 4, 1 and 5, and leaves friend 3. Both methods agree.

For n = 6 and k = 5, the seats are 0, 1, 0, 1, 1, 0, so the answer is 1. The simulation removes friends 5, 4, 6, 2 and 3, and leaves friend 1.

The value k can be larger than size. The % size wraps it, so no extra step is needed. For n = 5 and k = 7, both the recurrence and the simulation return 4.

Two index bases and the wrap

There are two numbering systems. The recurrence counts seats from 0, because % returns values from 0 to size - 1. The problem numbers the friends from 1. So the only place that converts between them is the last line, return winner + 1.

The wrap must use the size of the circle at that step. At size = 2 for n = 5 and k = 2, the shift is (0 + 2) % 2 = 0. With % n, the result would be (0 + 2) % 5 = 2, which is not a seat of a circle with two friends. This error carries forward, and the function returns 4 instead of 3.

The loop must reach n. range(2, n) stops at n - 1 and returns the winner of a smaller game. For n = 5 and k = 2, it returns 1 instead of 3.

The cost compared with simulating the circle

The recurrence runs one pass of n - 1 steps, and each step is one addition and one %. The time is O(N) and the space is O(1). The value of k does not change the cost.

A simulation keeps the friends in a list and removes one with people.pop(i). Each pop(i) moves every later friend one place to the left, so one removal costs O(N). There are n - 1 removals, so the time is O(N^2), and the list needs O(N) space.

For k = 2, the recurrence has a closed form: write n = 2^m + r, with 2^m the largest power of two that is at most n, and the winner is 2 * r + 1. For n = 5, 2^m = 4 and r = 1, so the winner is 3. This shortcut is only for k = 2. The loop works for any k.

60-Second Pitch

"After the first friend leaves, the remaining game is the same game with one friend fewer, and the count restarts k seats later. So if winner is the 0-indexed seat of the winner with size - 1 friends, then (winner + k) % size is the seat with size friends. I start from winner = 0 for one friend and loop size from 2 to n. At the end I return winner + 1, because the friends are numbered from 1. This takes O(N) time and O(1) space. A list.pop simulation takes O(N^2) time, because each removal shifts the list."

Common Questions

Why does removing one friend give a shift by k?: After the friend at seat (k - 1) % size leaves, the count restarts at seat k % size. If you relabel the circle so that this friend is seat 0, the game has size - 1 friends and starts at seat 0. A seat in the relabeled circle becomes a seat in the old circle by adding k and wrapping with % size.
What is the time and space complexity, and how does it compare with a simulation?: The recurrence takes O(N) time and O(1) space. A simulation with a list takes O(N^2) time, because each pop(i) shifts the later friends, and O(N) space for the list.
Why do you add 1 only at the end?: The recurrence uses seats from 0, because % returns values from 0 to size - 1. The problem numbers the friends from 1. Adding 1 inside the loop would break the wrap. So the conversion happens once, in the final return.
Does the code still work when k is larger than size?: Yes. The % size reduces any shift to a seat of the current circle. For n = 5 and k = 7, the recurrence and a full simulation both return 4.
Is there a faster formula?: For k = 2 only. Write n = 2^m + r, with 2^m the largest power of two that is at most n. The winner is 2 * r + 1, which is O(1) with bit operations. For n = 5 the winner is 3. For other values of k, the O(N) loop is the standard answer.

SWE Reasoning

Spot it

People or items stand in a circle, and every k-th one is removed until one is left.
The question asks who remains, not the order of removal. The recurrence gives the last survivor only.
Removing one item leaves the same game with one item fewer. Only the starting point changes.
A simulation with list.pop would work for small input, but the interviewer asks for O(N) time or for no extra list.
The numbering starts at 1 in the statement, and the formula needs numbering from 0.

The invariant, step by step

winner = 0 is the winner's seat in a circle of 1 friend. This is the starting invariant.
At the pass for size, winner is the winner's seat in the game with size - 1 friends. Seats are counted from 0.
In the game with size friends, friend at seat (k - 1) % size leaves first. The count then restarts at seat k % size.
The rest of the game is the smaller game, whose seat 0 is old seat k % size. So the smaller game's seat winner is old seat (winner + k) % size.
The assignment winner = (winner + k) % size makes winner the winner's seat for size friends. The invariant holds for the next pass.
After size = n, winner is the seat in the full circle. The line return winner + 1 converts it to a friend number.

Traps

Return winner without adding 1. The function returns the seat, not the friend number. For n = 5 and k = 2, it returns 2 instead of 3.
Wrap with % n. The circle at each step has size friends. With % n, the function returns 4 for n = 5 and k = 2, instead of 3.
Stop the loop at range(2, n). The last pass is missing, so the function answers for n - 1 friends. It returns 1 for n = 5 and k = 2.
Simulate with list.pop. The answer is correct, but each removal moves the later friends, so the time is O(N^2).

Practice

Canonical LeetCode:Find the Winner of the Circular Game (LC 1823)Elimination Game (LC 390)

Theory Context•Math & Geometry

Builds on Linear DP, which you haven’t finished yet.

P3MediumMental model~3 min speedrun

Josephus Problem (Circular Elimination Recurrence)

Find the Winner of the Circular Game (LC 1823)(opens leetcode.com)

n friends sit around a circle, labeled 1 through n going clockwise, so stepping clockwise past friend n wraps you straight back to friend 1.

Play unfolds like this:

Everyone begins with friend 1 as the current spot.
From there, tick off k friends moving clockwise, counting the current friend as the first tick -- looping around the circle again if k is larger than however many friends remain.
Whichever friend the k-th tick lands on is eliminated and steps out of the circle.
As long as two or more friends remain, the next round starts its count from the friend standing immediately clockwise of the one who just left.
Once only one friend is left, that friend is declared the winner.

Given n and k, work out which friend wins.

Example 1

Input:n = 5, k = 2

Output:3

Josephus Problem

circle of n friends ➔ smaller circle's winner ➔ shift by k

Spot it when: People (or items) stand in a circle and every k-th one is removed until one is left; find who remains without simulating every removal.

Josephus Problem

Python

1	def find_the_winner(n: int, k: int) -> int:
2	"""Find the Winner of the Circular Game (Josephus): f(size) = (f(size - 1) + k) % size.
3	Time: O(N) \| Space: O(1)
4	"""
5	winner = 0 # 0-indexed winner of the game with 1 friend
6	for size in range(2, n + 1):
7	winner = (winner + k) % size # Shift the smaller game's winner k seats
8	return winner + 1 # Friends are numbered from 1

Invariant: winner is always the 0-indexed seat of the winner of the game with size friends.

See it run

Find the Winner of the Circular Game with n = 5 and k = 2

size 1winner 0

Each column is one circle size. The top row lists its seats, and the bottom row is the winner's seat for that size.

prev the winner's seat in the smaller circle
new the winner's seat in this circle

With 1 friend in the circle, the only seat is seat 0. So winner = 0.

seats

0 to 0

0 to 1

0 to 2

0 to 3

0 to 4

winner seat

0new

1 / 8

Gotchas1 of 4

The trap
Gotcha 1: Returning winner without adding 1
Mistake
```
return winner
```
Fix
```
return winner + 1
```
What happens: The recurrence counts seats from 0. So winner = 0 is the only seat when one friend is left. Find the Winner of the Circular Game (LC 1823) numbers the friends from 1. Only the final return adds 1.
Example: n = 5, k = 2
Mistake: returns 2Fix: returns 3
Gotcha 2: Wrapping with % n instead of % size
Mistake
```
winner = (winner + k) % n
```
Fix
```
winner = (winner + k) % size
```
What happens: At each step, the circle has size friends, not n. The shift of k seats happens in that smaller circle, so the wrap must use % size. With % n, winner can point past the last seat of the current circle.
Example: n = 5, k = 2
Mistake: returns 4Fix: returns 3
Gotcha 3: Simulating the circle with list.pop
Mistake
```
people = list(range(1, n + 1))
i = 0
while len(people) > 1:
    i = (i + k - 1) % len(people)
    people.pop(i)
return people[0]
```
Fix
```
winner = 0
for size in range(2, n + 1):
    winner = (winner + k) % size
return winner + 1
```
What happens: The simulation gives the same answer, and it passes the limits of Find the Winner of the Circular Game (LC 1823). Each pop(i) shifts the later friends, so the simulation takes O(N^2) time and O(N) space. The recurrence takes O(N) time and O(1) space.
Gotcha 4: Looping range(2, n) instead of range(2, n + 1)
Mistake
```
for size in range(2, n):
```
Fix
```
for size in range(2, n + 1):
```
What happens: range stops before its end value. So range(2, n) stops at a circle of n - 1 friends. It returns the winner of that smaller game.
Example: n = 5, k = 2
Mistake: returns 1Fix: returns 3

Not this one if…

Players pass a ball up to 10^10 times, but nobody leaves and each pass goes to a fixed receiver[i], as in Maximize Value of Function in a Ball Passing Game (LC 2836): the step is not k seats in a shrinking circle, so jump ahead by powers of two instead. See Binary Lifting

Deep Dive

Why one removal turns the game into a smaller game

Building the answer from one friend upward

For n = 6 and k = 5, the seats are 0, 1, 0, 1, 1, 0, so the answer is 1. The simulation removes friends 5, 4, 6, 2 and 3, and leaves friend 1.

The value k can be larger than size. The % size wraps it, so no extra step is needed. For n = 5 and k = 7, both the recurrence and the simulation return 4.

Two index bases and the wrap

The loop must reach n. range(2, n) stops at n - 1 and returns the winner of a smaller game. For n = 5 and k = 2, it returns 1 instead of 3.

The cost compared with simulating the circle

The recurrence runs one pass of n - 1 steps, and each step is one addition and one %. The time is O(N) and the space is O(1). The value of k does not change the cost.

60-Second Pitch

Common Questions

Why does removing one friend give a shift by k?: After the friend at seat (k - 1) % size leaves, the count restarts at seat k % size. If you relabel the circle so that this friend is seat 0, the game has size - 1 friends and starts at seat 0. A seat in the relabeled circle becomes a seat in the old circle by adding k and wrapping with % size.
What is the time and space complexity, and how does it compare with a simulation?: The recurrence takes O(N) time and O(1) space. A simulation with a list takes O(N^2) time, because each pop(i) shifts the later friends, and O(N) space for the list.
Why do you add 1 only at the end?: The recurrence uses seats from 0, because % returns values from 0 to size - 1. The problem numbers the friends from 1. Adding 1 inside the loop would break the wrap. So the conversion happens once, in the final return.
Does the code still work when k is larger than size?: Yes. The % size reduces any shift to a seat of the current circle. For n = 5 and k = 7, the recurrence and a full simulation both return 4.
Is there a faster formula?: For k = 2 only. Write n = 2^m + r, with 2^m the largest power of two that is at most n. The winner is 2 * r + 1, which is O(1) with bit operations. For n = 5 the winner is 3. For other values of k, the O(N) loop is the standard answer.

SWE Reasoning

Spot it

People or items stand in a circle, and every k-th one is removed until one is left.
The question asks who remains, not the order of removal. The recurrence gives the last survivor only.
Removing one item leaves the same game with one item fewer. Only the starting point changes.
A simulation with list.pop would work for small input, but the interviewer asks for O(N) time or for no extra list.
The numbering starts at 1 in the statement, and the formula needs numbering from 0.

The invariant, step by step

winner = 0 is the winner's seat in a circle of 1 friend. This is the starting invariant.
At the pass for size, winner is the winner's seat in the game with size - 1 friends. Seats are counted from 0.
In the game with size friends, friend at seat (k - 1) % size leaves first. The count then restarts at seat k % size.
The rest of the game is the smaller game, whose seat 0 is old seat k % size. So the smaller game's seat winner is old seat (winner + k) % size.
The assignment winner = (winner + k) % size makes winner the winner's seat for size friends. The invariant holds for the next pass.
After size = n, winner is the seat in the full circle. The line return winner + 1 converts it to a friend number.

Traps

Return winner without adding 1. The function returns the seat, not the friend number. For n = 5 and k = 2, it returns 2 instead of 3.
Wrap with % n. The circle at each step has size friends. With % n, the function returns 4 for n = 5 and k = 2, instead of 3.
Stop the loop at range(2, n). The last pass is missing, so the function answers for n - 1 friends. It returns 1 for n = 5 and k = 2.
Simulate with list.pop. The answer is correct, but each removal moves the later friends, so the time is O(N^2).

Practice

Canonical LeetCode:Find the Winner of the Circular Game (LC 1823)Elimination Game (LC 390)

Theory Context•Math & Geometry

Builds on Linear DP, which you haven’t finished yet.

P3MediumMental model~3 min speedrun

Josephus Problem (Circular Elimination Recurrence)

Find the Winner of the Circular Game (LC 1823)(opens leetcode.com)

n friends sit around a circle, labeled 1 through n going clockwise, so stepping clockwise past friend n wraps you straight back to friend 1.

Play unfolds like this:

Everyone begins with friend 1 as the current spot.
From there, tick off k friends moving clockwise, counting the current friend as the first tick -- looping around the circle again if k is larger than however many friends remain.
Whichever friend the k-th tick lands on is eliminated and steps out of the circle.
As long as two or more friends remain, the next round starts its count from the friend standing immediately clockwise of the one who just left.
Once only one friend is left, that friend is declared the winner.

Given n and k, work out which friend wins.

Example 1

Input:n = 5, k = 2

Output:3

Josephus Problem

circle of n friends ➔ smaller circle's winner ➔ shift by k

Spot it when: People (or items) stand in a circle and every k-th one is removed until one is left; find who remains without simulating every removal.

Josephus Problem

Python

1	def find_the_winner(n: int, k: int) -> int:
2	"""Find the Winner of the Circular Game (Josephus): f(size) = (f(size - 1) + k) % size.
3	Time: O(N) \| Space: O(1)
4	"""
5	winner = 0 # 0-indexed winner of the game with 1 friend
6	for size in range(2, n + 1):
7	winner = (winner + k) % size # Shift the smaller game's winner k seats
8	return winner + 1 # Friends are numbered from 1

Invariant: winner is always the 0-indexed seat of the winner of the game with size friends.

See it run

Find the Winner of the Circular Game with n = 5 and k = 2

size 1winner 0

Each column is one circle size. The top row lists its seats, and the bottom row is the winner's seat for that size.

prev the winner's seat in the smaller circle
new the winner's seat in this circle

With 1 friend in the circle, the only seat is seat 0. So winner = 0.

seats

0 to 0

0 to 1

0 to 2

0 to 3

0 to 4

winner seat

0new

1 / 8

Gotchas1 of 4

The trap
Gotcha 1: Returning winner without adding 1
Mistake
```
return winner
```
Fix
```
return winner + 1
```
What happens: The recurrence counts seats from 0. So winner = 0 is the only seat when one friend is left. Find the Winner of the Circular Game (LC 1823) numbers the friends from 1. Only the final return adds 1.
Example: n = 5, k = 2
Mistake: returns 2Fix: returns 3
Gotcha 2: Wrapping with % n instead of % size
Mistake
```
winner = (winner + k) % n
```
Fix
```
winner = (winner + k) % size
```
What happens: At each step, the circle has size friends, not n. The shift of k seats happens in that smaller circle, so the wrap must use % size. With % n, winner can point past the last seat of the current circle.
Example: n = 5, k = 2
Mistake: returns 4Fix: returns 3
Gotcha 3: Simulating the circle with list.pop
Mistake
```
people = list(range(1, n + 1))
i = 0
while len(people) > 1:
    i = (i + k - 1) % len(people)
    people.pop(i)
return people[0]
```
Fix
```
winner = 0
for size in range(2, n + 1):
    winner = (winner + k) % size
return winner + 1
```
What happens: The simulation gives the same answer, and it passes the limits of Find the Winner of the Circular Game (LC 1823). Each pop(i) shifts the later friends, so the simulation takes O(N^2) time and O(N) space. The recurrence takes O(N) time and O(1) space.
Gotcha 4: Looping range(2, n) instead of range(2, n + 1)
Mistake
```
for size in range(2, n):
```
Fix
```
for size in range(2, n + 1):
```
What happens: range stops before its end value. So range(2, n) stops at a circle of n - 1 friends. It returns the winner of that smaller game.
Example: n = 5, k = 2
Mistake: returns 1Fix: returns 3

Not this one if…

Players pass a ball up to 10^10 times, but nobody leaves and each pass goes to a fixed receiver[i], as in Maximize Value of Function in a Ball Passing Game (LC 2836): the step is not k seats in a shrinking circle, so jump ahead by powers of two instead. See Binary Lifting

Deep Dive

Why one removal turns the game into a smaller game

Building the answer from one friend upward

For n = 6 and k = 5, the seats are 0, 1, 0, 1, 1, 0, so the answer is 1. The simulation removes friends 5, 4, 6, 2 and 3, and leaves friend 1.

The value k can be larger than size. The % size wraps it, so no extra step is needed. For n = 5 and k = 7, both the recurrence and the simulation return 4.

Two index bases and the wrap

The loop must reach n. range(2, n) stops at n - 1 and returns the winner of a smaller game. For n = 5 and k = 2, it returns 1 instead of 3.

The cost compared with simulating the circle

The recurrence runs one pass of n - 1 steps, and each step is one addition and one %. The time is O(N) and the space is O(1). The value of k does not change the cost.

60-Second Pitch

Common Questions

Why does removing one friend give a shift by k?: After the friend at seat (k - 1) % size leaves, the count restarts at seat k % size. If you relabel the circle so that this friend is seat 0, the game has size - 1 friends and starts at seat 0. A seat in the relabeled circle becomes a seat in the old circle by adding k and wrapping with % size.
What is the time and space complexity, and how does it compare with a simulation?: The recurrence takes O(N) time and O(1) space. A simulation with a list takes O(N^2) time, because each pop(i) shifts the later friends, and O(N) space for the list.
Why do you add 1 only at the end?: The recurrence uses seats from 0, because % returns values from 0 to size - 1. The problem numbers the friends from 1. Adding 1 inside the loop would break the wrap. So the conversion happens once, in the final return.
Does the code still work when k is larger than size?: Yes. The % size reduces any shift to a seat of the current circle. For n = 5 and k = 7, the recurrence and a full simulation both return 4.
Is there a faster formula?: For k = 2 only. Write n = 2^m + r, with 2^m the largest power of two that is at most n. The winner is 2 * r + 1, which is O(1) with bit operations. For n = 5 the winner is 3. For other values of k, the O(N) loop is the standard answer.

SWE Reasoning

Spot it

People or items stand in a circle, and every k-th one is removed until one is left.
The question asks who remains, not the order of removal. The recurrence gives the last survivor only.
Removing one item leaves the same game with one item fewer. Only the starting point changes.
A simulation with list.pop would work for small input, but the interviewer asks for O(N) time or for no extra list.
The numbering starts at 1 in the statement, and the formula needs numbering from 0.

The invariant, step by step

winner = 0 is the winner's seat in a circle of 1 friend. This is the starting invariant.
At the pass for size, winner is the winner's seat in the game with size - 1 friends. Seats are counted from 0.
In the game with size friends, friend at seat (k - 1) % size leaves first. The count then restarts at seat k % size.
The rest of the game is the smaller game, whose seat 0 is old seat k % size. So the smaller game's seat winner is old seat (winner + k) % size.
The assignment winner = (winner + k) % size makes winner the winner's seat for size friends. The invariant holds for the next pass.
After size = n, winner is the seat in the full circle. The line return winner + 1 converts it to a friend number.

Traps

Return winner without adding 1. The function returns the seat, not the friend number. For n = 5 and k = 2, it returns 2 instead of 3.
Wrap with % n. The circle at each step has size friends. With % n, the function returns 4 for n = 5 and k = 2, instead of 3.
Stop the loop at range(2, n). The last pass is missing, so the function answers for n - 1 friends. It returns 1 for n = 5 and k = 2.
Simulate with list.pop. The answer is correct, but each removal moves the later friends, so the time is O(N^2).

Practice

Canonical LeetCode:Find the Winner of the Circular Game (LC 1823)Elimination Game (LC 390)

Theory Context•Math & Geometry

Builds on Linear DP, which you haven’t finished yet.

P3MediumMental model~3 min speedrun

Josephus Problem (Circular Elimination Recurrence)

Find the Winner of the Circular Game (LC 1823)(opens leetcode.com)

n friends sit around a circle, labeled 1 through n going clockwise, so stepping clockwise past friend n wraps you straight back to friend 1.

Play unfolds like this:

Everyone begins with friend 1 as the current spot.
From there, tick off k friends moving clockwise, counting the current friend as the first tick -- looping around the circle again if k is larger than however many friends remain.
Whichever friend the k-th tick lands on is eliminated and steps out of the circle.
As long as two or more friends remain, the next round starts its count from the friend standing immediately clockwise of the one who just left.
Once only one friend is left, that friend is declared the winner.

Given n and k, work out which friend wins.

Example 1

Input:n = 5, k = 2

Output:3

Josephus Problem

circle of n friends ➔ smaller circle's winner ➔ shift by k

Spot it when: People (or items) stand in a circle and every k-th one is removed until one is left; find who remains without simulating every removal.

Josephus Problem

Python

1	def find_the_winner(n: int, k: int) -> int:
2	"""Find the Winner of the Circular Game (Josephus): f(size) = (f(size - 1) + k) % size.
3	Time: O(N) \| Space: O(1)
4	"""
5	winner = 0 # 0-indexed winner of the game with 1 friend
6	for size in range(2, n + 1):
7	winner = (winner + k) % size # Shift the smaller game's winner k seats
8	return winner + 1 # Friends are numbered from 1

Invariant: winner is always the 0-indexed seat of the winner of the game with size friends.

See it run

Find the Winner of the Circular Game with n = 5 and k = 2

size 1winner 0

Each column is one circle size. The top row lists its seats, and the bottom row is the winner's seat for that size.

prev the winner's seat in the smaller circle
new the winner's seat in this circle

With 1 friend in the circle, the only seat is seat 0. So winner = 0.

seats

0 to 0

0 to 1

0 to 2

0 to 3

0 to 4

winner seat

0new

1 / 8

Gotchas1 of 4

The trap
Gotcha 1: Returning winner without adding 1
Mistake
```
return winner
```
Fix
```
return winner + 1
```
What happens: The recurrence counts seats from 0. So winner = 0 is the only seat when one friend is left. Find the Winner of the Circular Game (LC 1823) numbers the friends from 1. Only the final return adds 1.
Example: n = 5, k = 2
Mistake: returns 2Fix: returns 3
Gotcha 2: Wrapping with % n instead of % size
Mistake
```
winner = (winner + k) % n
```
Fix
```
winner = (winner + k) % size
```
What happens: At each step, the circle has size friends, not n. The shift of k seats happens in that smaller circle, so the wrap must use % size. With % n, winner can point past the last seat of the current circle.
Example: n = 5, k = 2
Mistake: returns 4Fix: returns 3
Gotcha 3: Simulating the circle with list.pop
Mistake
```
people = list(range(1, n + 1))
i = 0
while len(people) > 1:
    i = (i + k - 1) % len(people)
    people.pop(i)
return people[0]
```
Fix
```
winner = 0
for size in range(2, n + 1):
    winner = (winner + k) % size
return winner + 1
```
What happens: The simulation gives the same answer, and it passes the limits of Find the Winner of the Circular Game (LC 1823). Each pop(i) shifts the later friends, so the simulation takes O(N^2) time and O(N) space. The recurrence takes O(N) time and O(1) space.
Gotcha 4: Looping range(2, n) instead of range(2, n + 1)
Mistake
```
for size in range(2, n):
```
Fix
```
for size in range(2, n + 1):
```
What happens: range stops before its end value. So range(2, n) stops at a circle of n - 1 friends. It returns the winner of that smaller game.
Example: n = 5, k = 2
Mistake: returns 1Fix: returns 3

Not this one if…

Players pass a ball up to 10^10 times, but nobody leaves and each pass goes to a fixed receiver[i], as in Maximize Value of Function in a Ball Passing Game (LC 2836): the step is not k seats in a shrinking circle, so jump ahead by powers of two instead. See Binary Lifting

Deep Dive

Why one removal turns the game into a smaller game

Building the answer from one friend upward

For n = 6 and k = 5, the seats are 0, 1, 0, 1, 1, 0, so the answer is 1. The simulation removes friends 5, 4, 6, 2 and 3, and leaves friend 1.

The value k can be larger than size. The % size wraps it, so no extra step is needed. For n = 5 and k = 7, both the recurrence and the simulation return 4.

Two index bases and the wrap

The loop must reach n. range(2, n) stops at n - 1 and returns the winner of a smaller game. For n = 5 and k = 2, it returns 1 instead of 3.

The cost compared with simulating the circle

The recurrence runs one pass of n - 1 steps, and each step is one addition and one %. The time is O(N) and the space is O(1). The value of k does not change the cost.

60-Second Pitch

Common Questions

Why does removing one friend give a shift by k?: After the friend at seat (k - 1) % size leaves, the count restarts at seat k % size. If you relabel the circle so that this friend is seat 0, the game has size - 1 friends and starts at seat 0. A seat in the relabeled circle becomes a seat in the old circle by adding k and wrapping with % size.
What is the time and space complexity, and how does it compare with a simulation?: The recurrence takes O(N) time and O(1) space. A simulation with a list takes O(N^2) time, because each pop(i) shifts the later friends, and O(N) space for the list.
Why do you add 1 only at the end?: The recurrence uses seats from 0, because % returns values from 0 to size - 1. The problem numbers the friends from 1. Adding 1 inside the loop would break the wrap. So the conversion happens once, in the final return.
Does the code still work when k is larger than size?: Yes. The % size reduces any shift to a seat of the current circle. For n = 5 and k = 7, the recurrence and a full simulation both return 4.
Is there a faster formula?: For k = 2 only. Write n = 2^m + r, with 2^m the largest power of two that is at most n. The winner is 2 * r + 1, which is O(1) with bit operations. For n = 5 the winner is 3. For other values of k, the O(N) loop is the standard answer.

SWE Reasoning

Spot it

People or items stand in a circle, and every k-th one is removed until one is left.
The question asks who remains, not the order of removal. The recurrence gives the last survivor only.
Removing one item leaves the same game with one item fewer. Only the starting point changes.
A simulation with list.pop would work for small input, but the interviewer asks for O(N) time or for no extra list.
The numbering starts at 1 in the statement, and the formula needs numbering from 0.

The invariant, step by step

winner = 0 is the winner's seat in a circle of 1 friend. This is the starting invariant.
At the pass for size, winner is the winner's seat in the game with size - 1 friends. Seats are counted from 0.
In the game with size friends, friend at seat (k - 1) % size leaves first. The count then restarts at seat k % size.
The rest of the game is the smaller game, whose seat 0 is old seat k % size. So the smaller game's seat winner is old seat (winner + k) % size.
The assignment winner = (winner + k) % size makes winner the winner's seat for size friends. The invariant holds for the next pass.
After size = n, winner is the seat in the full circle. The line return winner + 1 converts it to a friend number.

Traps

Return winner without adding 1. The function returns the seat, not the friend number. For n = 5 and k = 2, it returns 2 instead of 3.
Wrap with % n. The circle at each step has size friends. With % n, the function returns 4 for n = 5 and k = 2, instead of 3.
Stop the loop at range(2, n). The last pass is missing, so the function answers for n - 1 friends. It returns 1 for n = 5 and k = 2.
Simulate with list.pop. The answer is correct, but each removal moves the later friends, so the time is O(N^2).

Practice

Canonical LeetCode:Find the Winner of the Circular Game (LC 1823)Elimination Game (LC 390)