FastPrep
Problem · Array

Get Score Difference 🍊

Learn this problem
● EasyAmazon logoAmazonINTERNOA
See Amazon hiring insights

Problem statement

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

Function

getScoreDifference(values: int[]) → long

Examples

Example 1

values = [4, 1, 2, 3]return = 2
Example 1 illustration
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.

Example 2

values = [4, 1, 1, 4]return = 0
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.

Example 3

values = [1, 3, 3]return = 1
Player 1 picks 3, then Player 2 picks the other 3. Finally, Player 1 picks the remaining 1. The total difference in scores is: (3 + 1) - 3 = 1.

Constraints

  • 1 <= n <= 10^5
  • 1 <= values[i] <= 10^9

More Amazon problems

drafts saved locally
public long getScoreDifference(int[] values) {
  // write your code here
}
values[4, 1, 2, 3]
expected2
checking account