Round 1
Questions:
Given an array arr
that contains n
integers, the following operation can be performed on it any number of times (possibly zero):
- Choose any index
i
such that0 ≤ i < n - 1
and swaparr[i]
andarr[i + 1]
. Each element of the array can be swapped at most once during the whole process.
The strength of an index i
is defined as (arr[i] + 1) * (i + 1)
using 0-based indexing. Find the maximum possible sum of the strength of all indices after optimal swaps. Mathematically, maximize the following:
Sum = Σ (arr[i] * (i + 1))
Example:
Consider n = 4
, arr = [2, 1, 4, 3]
. It is optimal to swap arr[2]
and arr[3]
and arr[0]
and arr[1]
. The final array is [1, 2, 3, 4]
. The sum of strengths is 1*1 + 2*2 + 3*3 + 4*4 = 30
, which is the maximum possible. Thus, the answer is 30
.
Function Description:
Complete the function getMaximumSumOfStrengths
in the editor below.
getMaximumSumOfStrengths
has the following parameter:
int arr[]
: the initial array.
Testcases:
-
arr[] = [1, 9, 7, 3, 2]
→ Output is66
- Explanation: It is optimal to swap
arr[2]
andarr[3]
. The final array isarr[] = [1, 9, 3, 7, 2]
. The sum of strengths is1*1 + 2*9 + 3*3 + 4*7 + 5*2 = 66
.
- Explanation: It is optimal to swap
-
arr[] = [2, 1, 4, 3]
→ Output is30
-
arr[] = [1, 2, 5]
→ Output is20
Candidate's Approach
The candidate was able to solve the problem partially using a greedy approach. They focused on identifying optimal swaps that would maximize the sum of strengths based on the defined formula.
Interviewer's Feedback
No feedback provided.