Sam and Alex are playing a new game where there are number of piles, each with any number of stones in it. Players take turns removing stones from any one pile.
The number removed has to be either an integer multiple of a given number, k, where k > 0.
If there are fewer than k stones in a pile, any number can be removed.
Determine who wins the game.
Sam always starts, they both play optimally, and the last player to remove a stone wins. If Sam wins, return ” Sam wins the game of n pile(s). “, where n is the number of piles in the input. If Alex wins, return ” Alex wins the game of n pile(s). “.
For example, a game starts with n = 3 piles of stones that contain piles = [3, 5, 7] stones, and a constant k = 2. Sam will go first and remove 1 * k = 1 * 2 stones from the third pile leaving 7 – 2 = 5 stones in that pile.
Player Removes Result Start [3, 5, 7] Sam 2 [3, 5, 5] Alex 2 [3, 3, 5] Sam 2 [3, 3, 3] Alex 2 [1, 3, 3] Sam 2 [1, 1, 3] Alex 2 [1, 1, 1] Sam 1 [0, 1, 1] Alex 1 [0, 0, 1] Sam 1 [0, 0, 0]
In this case, Sam wins so ” Sam wins the game of 3 pile(s). ” is returned.
Function Description
Complete the function gameOfPiles in the editor below. The function must return a string that denotes the result of the game.
gameOfPiles has the following parameters:
1. piles[piles[0], piles[1],…piles[n-1]] : an array of integers, each piles[i] (where 0 ≤ i < n ) represents the number of stones in the i-th pile.
2. k: an integer
Constraints
1 ≤ n ≤ 105
1 ≤ piles[i] ≤ 1000
1 ≤ k ≤ 1000
Input Format For Custom Testing Sample Case 0
Sample Input For Custom Testing
2 2 2 1
Sample Output
Alex wins the game of 2 pile(s).
Explanation
There are multiple optimal scenarios for this game. Here is a scenario as an example where k = 1 .
Sam first removes 1 stone from the first pile, the configuration becomes [1, 2] .
Alex then removes 1 stone from the second pile, the configuration becomes [1, 1] .
Sam then removes 1 stone from the first pile, the configuration becomes [0, 1] .
At last, Alex removes 1 stone from the second pile, the configuration becomes [0, 0] .
Alex makes the last move so Alex wins.
Here:
Player Removes Result Start [3, 5, 7] Sam 2 [3, 5, 5] Alex 2 [3, 3, 5] Sam 2 [3, 3, 3] Alex 2 [1, 3, 3] Sam 2 [1, 1, 3] Alex 2 [1, 1, 1] Sam 1 [0, 1, 1] Alex 1 [0, 0, 1] Sam 1 [0, 0, 0]
Why not [3, 5, 3] after [3, 5, 7], rather than [3, 3, 5] ?
IGNORE PREV COMMENT!
Here:
Player Removes Result Start [3, 5, 7] Sam 2 [3, 5, 5] Alex 2 [3, 3, 5] Sam 2 [3, 3, 3] Alex 2 [1, 3, 3] Sam 2 [1, 1, 3] Alex 2 [1, 1, 1] Sam 1 [0, 1, 1] Alex 1 [0, 0, 1] Sam 1 [0, 0, 0]
Why not [3, 5, 3] after [3, 5, 5], rather than [3, 3, 5] ?