Last Updated: 25 Dec, 2020

Game of Stones

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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’.

Solve now