Element Swapping
Updated
Problem statement
A software development firm is hiring engineers and used the following challenge in its online test.
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(0 ≤iand swap arr[i] and arr[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] * (i + 1) using 0-based indexing. Find the maximum possible sum of the strengths of all indices after optimal swaps. Mathematically, maximize the following:
Complete the function getMaximumSumOfStrengths in the editor below.
getMaximumSumOfStrengths has the following parameter:
int arr[n]: the initial array
long integer: the maximum possible sum of strengths of all indices after the operations are applied optimally
Function
getMaximumSumOfStrengths(arr: int[]) → longExamples
Example 1
arr = [2, 1, 4, 3]return = 30It is optimal to swap (arr[2], arr[3]) and (arr[0], arr[1]). The final array is [1, 2, 3, 4], and the sum of strengths = (1 * 1 + 2 * 2 + 3 * 3 + 4 * 4) = 30, which is maximum possible. Thus, the answer is 30.
Constraints
- 1 ≤
n≤ 10^5 - 1 ≤
arr[i]≤ 10^5
More Canva interview questions
Similar questions at other companies
- Minimum Cost to Merge Values into OnePayPal · OAPayPal interview questions
- Minimum Operations to Sort with Rotations Then SwapsBank of New York Mellon · OA
- Minimum Cost of Left and Right PropagationAmazon · OA
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Reschedule Meetings for Maximum Free TimeFivetran · OAFivetran interview questions
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Maximum ScoreNVIDIA · OANVIDIA interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Minimize Adjacent Squared-Difference Cost with One InsertionMcKinsey & Company · OAMcKinsey & Company interview questions