387. Candy Jar Pickup Score

Candy Jar Pickup Score

A game has several jars containing candies. The player picks one candy during each turn.

On every turn, the player must pick a candy from the jar containing the greatest number of candies.

The score for the turn is the sum of the greatest candy count and the smallest positive candy count before the candy is picked.

After the pick, decrease the selected jar's candy count by one. Continue until the required number of picks is completed or every jar is empty. Return the total score.

Method

long calculateCandyScore( List<Integer> candiesInJars, int candyPicks )

candiesInJars contains the number of candies in each jar.
candyPicks is the maximum number of candies to pick.
Return the total score from all completed picks.

Rules

Determine the greatest and smallest positive counts before the current candy is picked.
Ignore empty jars when finding the smallest positive count.
If several jars have the greatest count, select the jar with the smallest index.
The same jar may provide both the greatest and smallest positive counts.
Each turn removes exactly one candy.
Stop early if every jar becomes empty.
No parameter value will be null.

Constraints

1 <= candiesInJars.size() <= 100,000
0 <= candiesInJars.get(i) <= 1,000,000,000
1 <= candyPicks <= 100,000
0 <= i < candiesInJars.size()

Examples

Example 1

calculateCandyScore( candiesInJars = List.of(3,1,5), candyPicks = 4 )

Output: 19

The four turn scores are 6, 5, 4, and 4.

Example 2

calculateCandyScore( candiesInJars = List.of(0,1,4), candyPicks = 6 )

Output: 16

Only five candies are available. Their turn scores are 5, 4, 3, 2, and 2. The game then stops.

Example 3

calculateCandyScore( candiesInJars = List.of(7), candyPicks = 3 )

Output: 36

The only jar provides both counts. The turn scores are 14, 12, and 10.

Example 4

calculateCandyScore( candiesInJars = List.of(2,2,2), candyPicks = 4 )

Output: 12

The four turn scores are 4, 3, 3, and 2.

Example 5

calculateCandyScore( candiesInJars = List.of(0,0,0,0), candyPicks = 10 )

Output: 0

Every jar is empty, so no candy is picked.