How should I practice Maximum Score?

Start by reading the full statement, solve the visible examples, then compare the pattern against related NVIDIA online assessment problems in FastPrep.

Is Maximum Score associated with NVIDIA?

FastPrep tags this as a NVIDIA online assessment coding practice problem when the problem catalog has that company and stage context.

Maximum Score

NVIDIA● MediumINTERNOA

Problem statement

You are given an array arr of positive integers and an integer k. Your score starts at 0.

Perform exactly k operations. In each operation:

Choose any index i and add the current value of arr[i] to your score.
Replace that element with ceil(arr[i] / 3), the smallest integer greater than or equal to one third of its current value.

Return the largest possible final score. You may choose the same index more than once. The total score may exceed a 32-bit integer.

Function

maxScore(arr: int[], k: int) → long

Examples

Example 1

arr = [10,10,10,10,10]k = 5return = 50

Select each of the five original values once. Each selection adds 10, for a total of 50. No operation can add more than 10.

Example 2

arr = [1,10,3,3,3]k = 3return = 17

Select 10, then its replacement 4, then one of the original 3 values. The score is 10 + 4 + 3 = 17. These are the three largest available gains.

Example 3

arr = [2]k = 5return = 6

The selected values are 2, 1, 1, 1, 1. The element stays at 1 after the first operation, and the total is 6.

Constraints

1 <= arr.length <= 10^5.
1 <= k <= 10^5.
1 <= arr[i] <= 10^9.