The Circular Chocolate Game

Easy

0/40

0 upvote

Asked in company

Problem statement

Two friends, Alice and Bob, are playing a game with N stacks of chocolates arranged in a circle. The stacks are numbered 0 to N-1 clockwise.

The rules of the game are as follows:

1) Alice always goes first.

2) The game starts with a pointer at stack 0.

3) On a player's turn, they must take exactly one chocolate from the stack indicated by the pointer.

4) After their turn, the pointer moves one position clockwise to the next stack.

5) If a player's turn begins and the pointer is at a stack that is already empty, that player has no valid move and loses the game immediately.

Given the initial number of chocolates in each stack, and assuming both Alice and Bob play optimally, your task is to determine the winner.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer N, the number of stacks.

The second line contains N space-separated integers, where the i-th integer represents the number of chocolates in stack i.

Output Format:

Print a single string, either Alice or Bob, who will win the game.

Note:

The game is deterministic; there are no choices for the players to make. The outcome is pre-determined by the initial setup.

The key to solving this efficiently is to realize that the game will proceed for a certain number of full "laps" around the circle until the first stack is about to be depleted. The minimum number of chocolates in any stack determines how many full laps can be completed without anyone losing.

The winner is determined by who gets stuck on the final, partial lap after all full laps are completed.

Sample Input 1:

3
5 8 2

Sample Output 1:

Bob

Explanation for Sample 1:

The minimum number of chocolates in any stack is 2 (in stack 2).
This means the game can proceed for 2 full laps around the circle without anyone losing.
Total turns after 2 laps = `2 * 3 = 6` turns.
The effective number of chocolates remaining are `{5-2, 8-2, 2-2}` = `{3, 6, 0}`.
Since 6 turns (0-indexed) have passed, and 6 is even, it is now Alice's (Player 1's) turn. The pointer is back at stack 0.
Turn 6 (Alice, Stack 0): Takes one chocolate. Remaining: `{2, 6, 0}`.
Turn 7 (Bob, Stack 1): Takes one chocolate. Remaining: `{2, 5, 0}`.
Turn 8 (Alice, Stack 2): The stack is empty. Alice has no move and loses. Bob wins.

Sample Input 2:

4
10 10 10 10

Sample Output 2:

Bob

Explanation for Sample 2:

All stacks have 10 chocolates. The game will proceed for a total of 40 turns.
Alice takes turns 0, 2, 4, ..., 38.
Bob takes turns 1, 3, 5, ..., 39.
The 40th turn (turn 39) is the last turn. Since 39 is odd, Bob makes the last move. Alice will then face turn 40, where the first stack she emptied is now empty again.
More simply, the total number of moves is 40. Alice makes moves 1, 3, ..., 39. Bob makes moves 2, 4, ..., 40. Bob makes the last valid move, so Alice loses. Bob wins.
Self-Correction: With 0-indexed turns, Bob takes turn 39.    The next turn is turn 40. It is Alice's turn, and the pointer is at stack `40 % 4 = 0`. Stack 0 is now empty. Alice loses. Bob wins.

Expected Time Complexity:

The expected time complexity is O(N), as it requires a single pass through the initial stacks.

Constraints:

1 <= N <= 10^5
1 <= chocolates[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

The Circular Chocolate Game

Time Complexity

Space Complexity

(100% EXP penalty)

The Circular Chocolate Game

Console