Number Game

Hard
0/120
Average time to solve is 10m
profile
Contributed by
17 upvotes
Asked in companies
SamsungGoldman Sachs

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2
2 3
2
5 3
Sample Output 1 :
Alice
Alice
Explanation of Sample Input 1
For the first test case, we have, initial set as { 2, 3}. Alice moves first, and the only move she can do is to choose 2 and 3, then to add 1 to the set. The new set is { 1, 2, 3 }. Next Bob moves, there is no valid move anymore, so the winner is Alice.

For the second test case, we have, initial set as { 3, 5}. Alice moves first, and the only move she can do is to choose 5 and 3, then to add 2 to the set. So, the new set is { 2, 3, 5 }. Next Bob moves, he cannot choose 2 and 5 as | 2 - 5 | = 3 is already in the set. He chooses 2 and 3 and adds 1 to the set. The new set is { 1, 2, 3, 5 }. Now, Alice can choose 1 and 5 and add 4 to the set. The new set is { 1, 2, 3, 4, 5 }. Next Bob moves, there is no valid move anymore, so the winner is Alice.
Sample Input 2 :
3
2
2 3
2
5 3
3
5 6 7
Sample Output 2 :
Alice
Alice
Bob
Hint

Think about the fact that the maximum number in the set will remain the same.

Approaches (1)
GCD 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.
Time Complexity

O( N* log( Max_Element ) ), where ‘N’ is the size of the initial set received in input.

 

Since we are calculating the GCD of all elements of the array, the overall Time Complexity is    O( N * log( Max_Element ) )

Space Complexity

O(N), where ‘N’ is the size of the initial set received in input.

 

Since we are storing the array, the overall Space Complexity is O(N).

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