1874. Minimize Product Sum of Two Arrays

Difficulty: Medium

The product sum of two equal-length arrays a and b is equal to the sum of a[i] * b[i] for all 0 <= i < a.length (0-indexed).

• For example, if a = [1,2,3,4] and b = [5,2,3,1], the product sum would be 1*5 + 2*2 + 3*3 + 4*1 = 22.

Given two arrays nums1 and nums2 of length n, return *the minimum product sum if you are allowed to rearrange the order of the elements in nums1*.

Example 1:

Input: nums1 = [5,3,4,2], nums2 = [4,2,2,5]

Output: 40

Explanation: We can rearrange nums1 to become [3,5,4,2]. The product sum of [3,5,4,2] and [4,2,2,5] is 3*4 + 5*2 + 4*2 + 2*5 = 40.

Example 2:

Input: nums1 = [2,1,4,5,7], nums2 = [3,2,4,8,6]

Output: 65

Explanation: We can rearrange nums1 to become [5,7,4,1,2]. The product sum of [5,7,4,1,2] and [3,2,4,8,6] is 5*3 + 7*2 + 4*4 + 1*8 + 2*6 = 65.

###Constraints:* n == nums1.length == nums2.length

• 1 <= n <= 10^5
• 1 <= nums1[i], nums2[i] <= 100

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <vector>

class Solution {
public:
    int minProductSum(std::vector<int>& nums1, std::vector<int>& nums2) {
        int cnt1[101] = { 0 };
        int cnt2[101] = { 0 };
        for (auto& num : nums1) {
            ++cnt1[num];
        }
        for (auto& num: nums2) {
            ++cnt2[num];
        }
        
        int n = nums1.size();
        int sum = 0;
        int a = 1, b = 100;
        for (int i = 0; i < n; ++i) {
            while (!cnt1[a]) {
                ++a;
            }
            while (!cnt2[b]) {
                --b;
            }
            sum += a * b;
            --cnt1[a];
            --cnt2[b];
        }
        return sum;
    }
};