Cheapest Product Sum

Medium

You are given two arrays first and second of the same length. Their product sum is first[0]·second[0] + first[1]·second[1] + …. You may rearrange the elements of first in any order, while second stays as it is. Return the smallest product sum you can get.

Example 1

first=[3, 1, 2], second=[4, 6, 5] → 28

Keep [3, 1, 2]: it puts 3 against 4, 1 against 6 and 2 against 5, for 12 + 6 + 10 = 28. That is the minimum: the largest value always faces the smallest one.

Example 2

first=[2, 2], second=[7, 1] → 16

With equal values in first the order does not matter: 2·7 + 2·1 = 16.

Example 3

first=[5], second=[9] → 45

Constraints

1 ≤ len(first) = len(second) ≤ 10⁵
1 ≤ first[i], second[i] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Biggest Number From Pieces Medium Studios for Recording Sessions Medium Low, High, Low Medium Strictly Low, High, Low Medium Fewest Meetings to Cancel Medium

Input

first=[3, 1, 2], second=[4, 6, 5]

Expected

Run checks the first 3 tests in your browser. Submit checks all 92 tests on the server, hidden ones included.