Given 2 arrays, find the minimal sum of multiplication of indexes

Question

Suppose I have 2 unsorted arrays of the same size, for example:

A = {1, 4, 3, 2}
B = {5, 12, 1, 5}

I would like to find the minimal sum of multiplying of every 2 cells - one from each array, meaning - the sum of A[i] * B[j] (i is an index in A, j is an index in B). which values should I multiply with which values from the other array in order to get that minimal sum of products?

(I hope it's clear that once you performed A[i]*A[j] you can't touch those cells again...)

edit: for the example above, the minimal sum is: 1*4 + 3*5 + 5*2 + 1*12 = 31

Answer 1

In order to find the smallest summation, order one set ascending, the other descending, and then multiply along the like indecies.

This is because the smallest possible product for each pairing a[i] * b[j] (for a fixed a[i] due to the need to have a result for each element) is the smallest possible value of b[j], and vice-versa.

This will also work with negatives because the greatest negative is the smallest number, and thus pairs with the most positive number from the corollary array. This further continues even when both sets are completely negative, because the result of each multiplication become equivalent to when both sets have the negatives of their values.