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
We want to minimize the sum of products, and as each number is non-negative, we want to pair the largest with the smallest. Thus, we can sort the arrays one in ascending and another in reversed order, then compute the dot product – which is the sum of the product.
GoLang: Minimize Product Sum of Two Arrays
Sorting in GoLang in reversed is a bit verbose – we need to sort.Reverse as the following.
1 2 3 4 5 6 7 8 9 | func minProductSum(nums1 []int, nums2 []int) int { sort.Ints(nums1) sort.Sort(sort.Reverse(sort.IntSlice(nums2))) var ans = 0 for i := 0; i < len(nums1); i ++ { ans += nums1[i] * nums2[i] } return ans } |
func minProductSum(nums1 []int, nums2 []int) int { sort.Ints(nums1) sort.Sort(sort.Reverse(sort.IntSlice(nums2))) var ans = 0 for i := 0; i < len(nums1); i ++ { ans += nums1[i] * nums2[i] } return ans }
Python: Minimize Product Sum of Two Arrays
Python implementation of computing the min product sum.
1 2 3 4 5 6 7 8 | class Solution: def minProductSum(self, nums1: List[int], nums2: List[int]) -> int: nums1.sort() nums2.sort(reverse=True) ans = 0 for i in range(len(nums1)): ans += nums1[i] * nums2[i] return ans |
class Solution: def minProductSum(self, nums1: List[int], nums2: List[int]) -> int: nums1.sort() nums2.sort(reverse=True) ans = 0 for i in range(len(nums1)): ans += nums1[i] * nums2[i] return ans
Alternatively, we can use the python one liner:
1 2 3 | class Solution: def minProductSum(self, nums1: List[int], nums2: List[int]) -> int: return sum([p*q for (p,q) in list(zip(sorted(nums1),sorted(nums2)[::-1]))]) |
class Solution: def minProductSum(self, nums1: List[int], nums2: List[int]) -> int: return sum([p*q for (p,q) in list(zip(sorted(nums1),sorted(nums2)[::-1]))])
All implementations take O(NLogN) time (where N is the total size length for two arrays) and O(1) space.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Backtracking Algorithm to Solve N Queens Puzzle (Partially Filled)
Next Post: Teaching Kids Programming - Rotate a 2D Matrix/Image 90 Degree Clockwise