How should I practice Obtain Maximum Score Using Minimum Swaps?

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

Is Obtain Maximum Score Using Minimum Swaps associated with infosys?

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

Problem · Greedy

Obtain Maximum Score Using Minimum Swaps

Learn this problem

● Medium

infosysOA

Problem statement

You are given an array arr containing an even number of distinct positive integers. You may swap any two positions in one operation.

After rearrangement, the score is the product of the sums of adjacent pairs:

(arr[0] + arr[1]) * (arr[2] + arr[3]) * ... * (arr[n - 2] + arr[n - 1]).

Return the minimum number of swaps needed to obtain the maximum possible score.

Function

minimumSwapsForMaximumScore(arr: int[]) → int

Examples

Example 1

arr = [4, 1, 2, 9, 3, 6]return = 2

For positive values, the maximum score is obtained by pairing the smallest value with the largest, the second-smallest with the second-largest, and so on. Here the required pairs are (1, 9), (2, 6), and (3, 4).

Swap 4 and 9 to obtain [9, 1, 2, 4, 3, 6].
Swap 4 and 6 to obtain [9, 1, 2, 6, 3, 4].

The adjacent pair sums are then 10, 8, and 7. The maximum score is reached in the minimum possible 2 swaps.

Constraints

arr.length is positive and even.
Every value in arr is a positive integer.
All values in arr are distinct.