Problem Brief
Get Score Difference 🍊
INTERNOA
See Amazon online assessment and hiring insightsAmazon Games has recently unveiled a two-player competitive game featuring a collection of positive integers, each symbolizing a score value.
On each turn, a player selects any number from the collection, adds it to their personal score, and removes that number from the collection. The players take alternate turns, with Player 1 always starting the game. This process repeats until there are no numbers left.
Both players aim to maximize their own scores by making optimal choices.
Your task is to compute the absolute difference between the final scores of both players, assuming both play in the best possible way.
1Example 1
Input
values = [4, 1, 2, 3]
Output
2
Explanation
The game goes as 👇
The gameplay unfolds as follows:
Player 1 picks 4 (total score: 4)
Player 2 selects 3 (total score: 3)
Player 1 picks 2 (total score: 4 + 2 = 6)
Player 2 selects 1 (total score: 3 + 1 = 4)
At this point, the array is fully exhausted. GAME OVER ✋
The final result is the difference between their scores: 6 - 4 = 2.
2Example 2
Input
values = [4, 1, 1, 4]
Output
0
Explanation
Player 1 selects 4, then Player 2 also picks 4.
Next, Player 1 chooses 1, and Player 2 picks 1 as well.
The final score difference is: (4 + 1) - (4 + 1) = 0.
3Example 3
Input
values = [1, 3, 3]
Output
1
Explanation
The first player takes 4, followed by the second player also choosing 4.
After that, the first player picks 1, and the second player selects 1 as well.
The total difference in scores is: (4 + 1) - (4 + 1) = 0.
Constraints
Limits and guarantees your solution can rely on.
1 <= n <= 10^51 <= values[i] <= 10^9