Last Updated: 11 Dec, 2020

Number Game

Hard

Asked in companies

Solve now

Problem statement

Alice and Bob have invented a new game to play. The rules are as follows -

First, they get a set of ‘N’ distinct integers. And then they take turns to make the following moves. During each move, either Alice or Bob (the player whose turn is the current) can choose two distinct integers ‘X’ and ‘Y’ from the set, such that the set doesn't contain their absolute difference |X - Y|. Then this player adds integer |X - Y| to the set (so, the size of the set increases by one).

If the current player has no valid move, he (or she) loses the game. The question is who will finally win the game if both players play optimally. Remember that Alice always moves first.

Input Format :

The first line contains a single integer T representing the number of test cases. Then test cases follow:

The first line contains an integer ‘N’ representing the size of the array.
The second line contains N space-separated distinct integers denoting the elements of the array.

Output Format :

For each test case, print the name of the winner i.e. "Alice" or "Bob" (without quotes).

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
2 <= N <= 10^5
1 <= array[i] <= 10^9

Time Limit : 1 sec

Solve now

Approaches

01 Approach

Approach :

First, we notice that we are inserting the difference between two integers in the set, so it will always be less than the maximum element of the set.
Secondly, the difference between two integers ‘X’ and ‘Y’ will always be a multiple of their GCD.
So, no matter what elements we add to the set, the GCD of all elements of the set will be the same as that initially.
So, we can say that the total integers present in the set after performing all the moves will be equal to the maximum element of the set divided by the GCD of the set.
Hence, total elements added will be equal to maximum_element/GCD_of_the_set - N .
This is equal to the number of moves made and if moves are even, Bob is the winner.
Otherwise, Alice is the winner.

Algorithm :

Initialise ‘gcd’ = 0.
We calculate the gcd of all the elements of the set and track it in ‘gcd’.
Set ‘maximum_element’ as the maximum element of the set.
Initialize ‘total_moves’=( maximum_element / gcd ) - N.
If ‘total_moves’ is odd,
Alice is the winner.
Else, Bob is the winner.

Solve now