Last Person Left in a Counting Circle
Updated
Problem statement
There are n people standing in a circle, numbered 1 to n clockwise. After person n comes person 1 again.
The game goes like this:
- Start at person
1. - Count
kpeople clockwise, counting the person you start at as 1. The count wraps around the circle as many times as needed. - The
k-th person counted leaves the circle. - If more than one person is left, start again at the person just clockwise of the one who left, and go back to step 2.
Return the number of the last person left in the circle.
Function
findTheWinner(n: int, k: int) → intExamples
Example 1
n = 7k = 4return = 2Counting starts at person 1. The 4th person counted each time leaves: 4, then 1 (counting 5, 6, 7, 1), then 6, then 5, then 7, then 3. Person 2 is left.
Example 2
n = 3k = 5return = 1k can be larger than the circle. Counting 1, 2, 3, 1, 2 makes person 2 leave. Counting goes on from person 3: 3, 1, 3, 1, 3, so person 3 leaves and person 1 is left.
Example 3
n = 8k = 1return = 8With k = 1, the first person counted always leaves, so people leave in order 1, 2, 3, ..., 7 and person 8 is left.
Constraints
1 <= n <= 10^61 <= k <= 10^9
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Path Between Two Nodes of a Fibonacci TreeDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Babysitter Quote with Hourly RatesUpstart · ONSITE INTERVIEWUpstart interview questions
- Expected Value of Modified DiceJane Street · ONSITE INTERVIEWJane Street interview questions
- Fractional Share Inventory FlatteningRobinhood · PHONE SCREEN · ONSITE INTERVIEWRobinhood interview questions
- Merge Sort Report with a Noisy ComparatorMercor · ONSITE INTERVIEWMercor interview questions
- Reservoir Sampling with Recorded DrawsMeta · ONSITE INTERVIEWMeta interview questions
- Group-Relative Policy AdvantagesAmazon · ONSITE INTERVIEW
- Reservoir Sampling with Recorded DrawsStackAdapt · ONSITE INTERVIEWStackAdapt interview questions
- Iterate Canonical IPv6 AddressesOpenAI · ONSITE INTERVIEWOpenAI interview questions
- Nth Staged License PlateGoogle · ONSITE INTERVIEWGoogle interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)