FastPrepSum Max Plus Min After Decrement Operations

Sum Max Plus Min After Decrement Operations

Amazon logoAmazon● MediumINTERNOA
Learn

Problem statement

You are given an integer array arr and an integer requests.

Repeat the following operation exactly requests times:

  • Find the current maximum value and the current minimum value in arr.
  • Add their sum to the answer.
  • Choose one occurrence of the maximum value and decrease it by 1.

Return the final accumulated answer.

Function

sumMaxPlusMinAfterOperations(arr: int[], requests: int) → long

Complete the function sumMaxPlusMinAfterOperations in the editor below.

sumMaxPlusMinAfterOperations has the following parameters:

  • int[] arr: the initial values
  • int requests: the number of operations
  • Returns long: the accumulated sum

Examples

Example 1

arr = [1, 2]requests = 2return = 5

First add 1 + 2 = 3 and decrement the 2 to 1. Then add 1 + 1 = 2. The total is 5.

Example 2

arr = [3, 3, 3]requests = 1return = 6

The current maximum and minimum are both 3, so the answer increases by 6.

Constraints

  • 1 <= arr.length <= 105
  • 1 <= arr[i] <= 109
  • 0 <= requests <= 109
  • Each operation decreases one occurrence of the current maximum value by exactly 1.
  • Use a wide enough integer type (e.g., long) for the accumulated total.

More Amazon problems

See Amazon hiring insights
public long sumMaxPlusMinAfterOperations(int[] arr, int requests) {
    // write your code here
}
arr[1, 2]
requests2
expected5
Checking account…