Game of Stones

Easy
0/40
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in companies
AmazonCoinbaseSamsung

Problem statement

Given the count of total stones in a game. Two-player ‘Ale’ and ‘Bob’ are playing the game. Your task is to find who will win the game if both the players are playing optimally.

Rules of the game.

1. In a single turn, a player can choose a single stone or ‘even’ number of stones.

2. They will play alternatively, which means in the first chance ‘Ale’ will collect the stones, in second-chance ‘Bob’ will collect the stones. And always ‘Ale’ will start the game.

3. If any player is not able to take any stones then another player will win the game.

Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer,  which denotes the total number of stones in the game.
Output Format: 
For each test case, return a string ‘Ale’ or ‘Bob’ according to your answer.
Note: 
1. Do not print anything, just return ‘Ale’ if ‘Ale’ will win the game else return ‘Bob’.
Constraints: 
1 <= T <= 10^5
1 <= number of stones <= 10^9

Where ‘T’ is the total number of test cases.
Time limit: 1 second
Sample Input 1:
2
2
3
Sample Output 1:
Ale
Bob
Explanation of sample input 1:
Test Case 1:

Given the number of stones is ‘2’.
Then first player ‘Ale’ can choose both the stones because 2 is an even number.
So ‘Ale’ will the game.
Return ‘Ale’.

Test Case 2:

Given the number of stones is ‘3’.
In the first turn ‘Ale’ can choose ‘1’ stone or ‘2’ store, but not ‘3’ stone because ‘3’ is neither ‘1’ or even number.
If ‘Ale’ chooses ‘1’ in the first turn. Then in the second turn, ‘Bob’ will collect the remaining ‘2’ stone, so ‘Bob’ will win.
If ‘Ale’ chooses ‘2’ stones in the first turn. Then in the second turn, ‘Bob’ will collect the remaining ‘1’ stone, again ‘Bob’ will win the game.
So in both cases ‘Bob’ is winning the game. Hence Return ‘Bob’.
Sample Input 2:
2
4
6
Sample Output 2:
Ale
Ale
Hint

Find cases when ‘Ale’ can lose the game.

Approaches (1)
Game Theory
  • It is clear that if the number of stones is ‘1’ then ‘Ale’ wins the game. If ‘2’ then also ‘Ale’ wins the match, and if ‘3’ then ‘Bob’ wins the game.
  • So we can observe that, if anyone has a chance to choose a stone from ‘3’ number of stones then another opponent will the game. If ‘Ale’ choosing the stones from ‘3’ number stone then ‘Bob’ will win and vice versa.
  • If the number of stones is ‘4’ then ‘Ale’ will win the game because ‘4’ is an even number and he chooses all the ‘4’ stones in the first turn.
  • If the number of stones is ‘5’, and ‘Ale’ playing optimally then he knows that if any turns you have a chance to choose stones from ‘3’ then you will lose the game.
  • Then ‘Ale’ choose the ‘2’ stones, if next turn ‘Bob’ has a chance to chose stones from remaining ‘5-2 =3’ stones, and in the of ‘3’ stone current player always lose the game then in ‘Ale’ will win the game.
  • Same for all the other number, If the number of stones is even then ‘Ale’ choose all the stones, if odd then ‘Ale’ will choose ‘n -3’ in the first turn, because ‘n’ is odd then ‘n-3’ is an even number, for the next turn of ‘Bob’ there will be remaining only ‘3’ number of stones. And ‘Bob’ will lose the game.

Code -

  • If the given number of stones is ‘3’ then return ‘Bob’.
  • Else return ‘Ale’.

 

Time Complexity

0(1), we are taking a constant time.

Space Complexity

O(1), we are using constant space. 

Code Solution
(100% EXP penalty)
Game of Stones
Full screen
Console