<blockquote> 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 </blockquote> 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 <a href="https://helloacm.com/algorithms-to-compute-the-dot-product-of-two-sparse-vectors/" title="Algorithms to Compute the Dot Product of Two Sparse Vectors">dot product</a> - which is the sum of the product. <h3>GoLang: Minimize Product Sum of Two Arrays</h3> Sorting in GoLang in reversed is a bit verbose - we need to sort.Reverse as the following. <pre lang=c> 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 } </pre> <h3>Python: Minimize Product Sum of Two Arrays</h3> Python implementation of computing the min product sum. <pre lang=py> 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 </pre> Alternatively, we can use the python one liner: <pre lang=py> 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]))]) </pre> All implementations take O(NLogN) time (where N is the total size length for two arrays) and O(1) space. Reposted from [Blog](https://helloacm.com/algorithm-to-minimize-product-sum-of-two-arrays/) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Thank you for reading ^^^^^^^^^^^^^^^ --------------- ## NEW! [Following my Trail (Upvote or/and Downvote)](https://steemit.com/witness-category/@justyy/following-my-trail-upvote-or-and-downvote-by-authorizing-posting-key-to-me) Follow me for topics of *Algorithms, Blockchain and Cloud.* I am @justyy - a Steem Witness [https://steemyy.com](https://steemyy.com) #### My contributions - [Video Downloader](https://weibomiaopai.com/download-video-parser.php) - [Steem Blockchain Tools](https://steemyy.com) - [Free Cryptos API](https://steemit.com/witness-category/@justyy/serverless-api-to-query-the-cryptos-and-fiat) - [VPS Database](https://anothervps.com/vps-database/) - [Computing Technology Blog](https://helloacm.com) - [A few useless tools](https://helloacm.com/tools/) - [And some other online software/tools](https://steakovercooked.com/Software.Home) - [Merge Files/Videos](https://slowapi.com/merge-videos/) - [LOGO Turtle Programming Chrome Extension](https://chrome.google.com/webstore/detail/logo-turtle-graphics/dcoeaobaokbccdcnadncifmconllpihp) - [Teaching Kids Programming - Youtube Channel](https://www.youtube.com/channel/UCK2ugmUOoYne1qQfSAph4nQ?view_as=subscriber) and [All Contents](https://github.com/DoctorLai/Teaching-Kids-Programming/blob/main/README.md) #### Delegation Service 1. [Voting Algorithm Updated to Favor those High Delegations!](https://steemit.com/wherein/@justyy/voting-algorithm-updated-to-favor-those-high-delegations) - Delegate 1000 to justyy: [Link](https://steemyy.com/sp-delegate-form/?delegatee=justyy&amount=1000) - Delegate 5000 to justyy: [Link](https://steemyy.com/sp-delegate-form/?delegatee=justyy&amount=5000) - Delegate 10000 to justyy: [Link](https://steemyy.com/sp-delegate-form/?delegatee=justyy&amount=10000) #### Support me If you like my work, please: - [Buy Me a Coffee](https://justyy.com/out/buymeacoffee), Thanks! - [Become my Sponsor](https://github.com/sponsors/DoctorLai), Thanks! - Voting for me: https://steemit.com/~witnesses type in **justyy** and click ***VOTE*** https://steemyy.com/images/vote-for-justyy.jpg 1. Delegate SP: https://steemyy.com/sp-delegate-form/?delegatee=justyy 2. Vote @justyy as Witness: https://steemyy.com/witness-voting/?witness=justyy&action=approve 3. Set @justyy as Proxy: https://steemyy.com/witness-voting/?witness=justyy&action=proxy Alternatively, you can vote witness or set proxy here: https://steemit.com/~witnesses -------------
post_id | 91,793,086 |
---|---|
author | justyy |
permlink | algorithm-to-minimize-product-sum-of-two-arrays |
category | programming |
json_metadata | {"tags":["programming","coding","sct","whalepower","blog","algorithms","upmefund","zzan"],"users":["justyy"],"image":["https:\/\/steemyy.com\/images\/vote-for-justyy.jpg"],"links":["https:\/\/helloacm.com\/algorithms-to-compute-the-dot-product-of-two-sparse-vectors\/","https:\/\/helloacm.com\/algorithm-to-minimize-product-sum-of-two-arrays\/","https:\/\/steemit.com\/witness-category\/@justyy\/following-my-trail-upvote-or-and-downvote-by-authorizing-posting-key-to-me","https:\/\/steemyy.com","https:\/\/weibomiaopai.com\/download-video-parser.php","https:\/\/steemit.com\/witness-category\/@justyy\/serverless-api-to-query-the-cryptos-and-fiat","https:\/\/anothervps.com\/vps-database\/","https:\/\/helloacm.com","https:\/\/helloacm.com\/tools\/","https:\/\/steakovercooked.com\/Software.Home","https:\/\/slowapi.com\/merge-videos\/","https:\/\/chrome.google.com\/webstore\/detail\/logo-turtle-graphics\/dcoeaobaokbccdcnadncifmconllpihp","https:\/\/www.youtube.com\/channel\/UCK2ugmUOoYne1qQfSAph4nQ?view_as=subscriber","https:\/\/github.com\/DoctorLai\/Teaching-Kids-Programming\/blob\/main\/README.md","https:\/\/steemit.com\/wherein\/@justyy\/voting-algorithm-updated-to-favor-those-high-delegations","https:\/\/steemyy.com\/sp-delegate-form\/?delegatee=justyy&amount=1000","https:\/\/steemyy.com\/sp-delegate-form\/?delegatee=justyy&amount=5000","https:\/\/steemyy.com\/sp-delegate-form\/?delegatee=justyy&amount=10000","https:\/\/justyy.com\/out\/buymeacoffee","https:\/\/github.com\/sponsors\/DoctorLai","https:\/\/steemit.com\/~witnesses","https:\/\/steemyy.com\/sp-delegate-form\/?delegatee=justyy","https:\/\/steemyy.com\/witness-voting\/?witness=justyy&action=approve","https:\/\/steemyy.com\/witness-voting\/?witness=justyy&action=proxy"],"app":"steemit\/0.2","format":"markdown"} |
created | 2021-06-08 08:10:42 |
last_update | 2021-06-08 08:10:42 |
depth | 0 |
children | 0 |
net_rshares | 35,944,774,754,613 |
last_payout | 2021-06-15 08:10:42 |
cashout_time | 1969-12-31 23:59:59 |
total_payout_value | 14.322 SBD |
curator_payout_value | 13.759 SBD |
pending_payout_value | 0.000 SBD |
promoted | 0.000 SBD |
body_length | 5,113 |
author_reputation | 1,990,164,104,714,661 |
root_title | "Algorithm to Minimize Product Sum of Two Arrays" |
beneficiaries | [] |
max_accepted_payout | 1,000,000.000 SBD |
percent_steem_dollars | 10,000 |
author_curate_reward | "" |
voter | weight | wgt% | rshares | pct | time |
---|---|---|---|---|---|
gerber | 0 | 796,781,618 | 4.59% | ||
ezzy | 0 | 58,649,712,318 | 4.59% | ||
nascimentoab | 0 | 5,432,386 | 12.5% | ||
exyle | 0 | 3,813,572,099 | 4.59% | ||
ace108 | 0 | 225,892,416,328 | 18% | ||
psygambler | 0 | 1,745,473,392 | 12.5% | ||
xiaohui | 0 | 3,992,607,634 | 100% | ||
shanghaipreneur | 0 | 60,895,150,288 | 100% | ||
samzung | 0 | 478,681,493 | 12.5% | ||
jlufer | 0 | 8,295,673,772 | 100% | ||
justyy | 0 | 32,566,147,478,697 | 100% | ||
happyukgo | 0 | 15,702,425,920 | 100% | ||
fleur | 0 | 29,723,275,602 | 100% | ||
lebah | 0 | 330,533,631 | 12.5% | ||
gunthertopp | 0 | 368,002,111,186 | 6.25% | ||
shebe | 0 | 141,263,561 | 12.5% | ||
catwomanteresa | 0 | 395,629,605 | 100% | ||
khalil319 | 0 | 245,820,274 | 10% | ||
oldman28 | 0 | 26,139,468,597 | 60% | ||
ahlawat | 0 | 12,095,382,323 | 11% | ||
aafeng | 0 | 3,197,782,150 | 30% | ||
elenasteem | 0 | 370,825,731 | 100% | ||
floatinglin | 0 | 5,097,972,213 | 100% | ||
mrspointm | 0 | 20,038,430,682 | 100% | ||
accelerator | 0 | 22,564,751,550 | 4.59% | ||
acactus1013 | 0 | 2,178,108,678 | 100% | ||
rosatravels | 0 | 28,905,026,521 | 100% | ||
deathwing | 0 | 417,386,782 | 11.48% | ||
superbing | 0 | 3,923,669,516 | 100% | ||
dailyfortune | 0 | 3,190,247,423 | 100% | ||
dailystats | 0 | 5,076,549,233 | 100% | ||
daisyphotography | 0 | 217,450,240 | 100% | ||
khaleelkazi | 0 | 215,754,729 | 4.59% | ||
jianan | 0 | 33,522,562,849 | 100% | ||
cnbuddy | 0 | 991,041,387,363 | 100% | ||
chekohler | 0 | 133,483,061 | 12.5% | ||
anxin | 0 | 9,250,375,853 | 100% | ||
linlada639 | 0 | 14,071,888,392 | 40% | ||
steeminer4up | 0 | 0 | 12.5% | ||
toufiqsoudagar | 0 | 47,505,742 | 12.5% | ||
awuahbenjamin | 0 | 3,383,962,195 | 100% | ||
mmmmkkkk311 | 0 | 252,248,192,273 | 100% | ||
nealmcspadden | 0 | 3,408,590,740 | 4.59% | ||
mermaidvampire | 0 | 1,250,041,700 | 100% | ||
hokulor | 0 | 0 | 6.25% | ||
kimjaguar | 0 | 1,683,454,652 | 12.5% | ||
foodielifestyle | 0 | 33,169,856,463 | 100% | ||
woolfe19861008 | 0 | 2,119,991,088 | 100% | ||
yuxuan | 0 | 23,767,508,453 | 100% | ||
penderis | 0 | 3,026,351,468 | 100% | ||
blockchaindaily | 0 | 400,715,666 | 1% | ||
ethanlee | 0 | 4,677,963,846 | 100% | ||
peerzadazeeshan | 0 | 1,560,094,733 | 12.5% | ||
wonsama | 0 | 11,322,519,556 | 100% | ||
kgakakillerg | 0 | 3,692,583,926 | 10% | ||
krnews | 0 | 400,819,304 | 100% | ||
goktug0814 | 0 | 183,272,187 | 20% | ||
pattoounlimited | 0 | 509,546,076 | 12.5% | ||
sweet-jenny8 | 0 | 20,179,720,766 | 100% | ||
myskye | 0 | 14,094,803,986 | 100% | ||
wbot01 | 0 | 138,121,783 | 100% | ||
sgbonus | 0 | 12,544,223,313 | 100% | ||
ihal0001 | 0 | 216,867,927 | 12.5% | ||
chineselaw | 0 | 151,258,755 | 100% | ||
diegopadilla | 0 | 1,025,264,658 | 12.5% | ||
torbrowser | 0 | 57,869,437 | 25% | ||
laiyuehta | 0 | 4,861,436,436 | 100% | ||
turtlegraphics | 0 | 2,360,598,858 | 100% | ||
glory7 | 0 | 61,640,754,754 | 100% | ||
dlike | 0 | 13,461,363,746 | 6% | ||
witnesstools | 0 | 6,863,419,437 | 100% | ||
doctor.strange | 0 | 142,124,845 | 100% | ||
dead.pool | 0 | 145,967,483 | 100% | ||
black.widow | 0 | 137,185,657 | 100% | ||
marvel.spiderman | 0 | 137,331,540 | 100% | ||
marvel.hulk | 0 | 137,220,620 | 100% | ||
marvel.ironman | 0 | 137,405,754 | 100% | ||
black.pan.ther | 0 | 137,588,297 | 100% | ||
ilovecoding | 0 | 6,454,796,603 | 100% | ||
smokingfit | 0 | 3,295,386,827 | 100% | ||
sapwood | 0 | 195,169,634,038 | 100% | ||
claim7 | 0 | 136,724,532 | 100% | ||
wcasino | 0 | 165,314,848 | 100% | ||
wcasino.pay | 0 | 136,975,558 | 100% | ||
wcasino.holdem | 0 | 41,351,449 | 100% | ||
wcasino.jackpot | 0 | 12,078,701 | 100% | ||
steemfuckeos | 0 | 3,091,633,271 | 100% | ||
steemit.holdem | 0 | 48,046,796 | 100% | ||
steemit.jackpot | 0 | 12,080,407 | 100% | ||
bluesniper | 0 | 1,490,483,970 | 5% | ||
deer3 | 0 | 22,177,201,831 | 100% | ||
smcard | 0 | 37,477,576 | 100% | ||
smonsmon | 0 | 36,882,254 | 100% | ||
guro | 0 | 37,142,867 | 100% | ||
shindorim | 0 | 36,808,590 | 100% | ||
yongsan | 0 | 37,033,148 | 100% | ||
incheon | 0 | 37,555,526 | 100% | ||
mapo | 0 | 36,850,534 | 100% | ||
shingil | 0 | 25,607,688 | 100% | ||
checkname | 0 | 37,180,210 | 100% | ||
starterpack | 0 | 25,534,919 | 100% | ||
gdragon | 0 | 37,071,022 | 100% | ||
sumimasen | 0 | 37,257,652 | 100% | ||
smtester | 0 | 36,888,671 | 100% | ||
showdown | 0 | 25,275,518 | 100% | ||
monstersteem | 0 | 37,182,982 | 100% | ||
freesale | 0 | 36,994,924 | 100% | ||
freefee | 0 | 36,811,063 | 100% | ||
testsama | 0 | 25,462,913 | 100% | ||
ctime | 0 | 64,456,742,785 | 5% | ||
kimch | 0 | 25,088,988 | 100% | ||
tongdak | 0 | 37,593,883 | 100% | ||
hanbok | 0 | 47,899,742 | 100% | ||
jjangjjangman | 0 | 24,980,143 | 100% | ||
superguard | 0 | 46,891,880 | 100% | ||
yawang | 0 | 24,867,570 | 100% | ||
roadmap | 0 | 25,203,212 | 100% | ||
kpay | 0 | 24,313,624 | 100% | ||
adultbaby | 0 | 37,072,979 | 100% | ||
sneack | 0 | 25,240,810 | 100% | ||
gzone | 0 | 36,955,087 | 100% | ||
ppororo | 0 | 37,254,860 | 100% | ||
lotto645 | 0 | 25,053,493 | 100% | ||
alphamonsters | 0 | 36,625,157 | 100% | ||
betamonsters | 0 | 37,328,386 | 100% | ||
girlfriends | 0 | 36,884,001 | 100% | ||
fastway | 0 | 36,406,638 | 100% | ||
smonsang | 0 | 24,868,534 | 100% | ||
technomart | 0 | 36,810,885 | 100% | ||
lastsmon | 0 | 25,128,907 | 100% | ||
postme | 0 | 36,404,361 | 100% | ||
smilezone | 0 | 35,919,907 | 100% | ||
bearbaby | 0 | 36,551,405 | 100% | ||
o0o0o | 0 | 52,186,367 | 100% | ||
thecards | 0 | 36,510,988 | 100% | ||
developments | 0 | 36,256,929 | 100% | ||
originals | 0 | 36,922,840 | 100% | ||
beanpole | 0 | 36,810,369 | 100% | ||
oilbank | 0 | 36,771,620 | 100% | ||
iliili | 0 | 36,440,952 | 100% | ||
kotlin | 0 | 36,292,375 | 100% | ||
flutters | 0 | 36,624,240 | 100% | ||
prettyguy | 0 | 36,439,182 | 100% | ||
skymin | 0 | 58,221,853,846 | 35% | ||
gamemonsters | 0 | 51,890,532 | 100% | ||
blueguy | 0 | 128,455,270 | 100% | ||
sicbo | 0 | 151,007,978 | 100% | ||
yaoi | 0 | 163,346,545 | 100% | ||
farmfarm | 0 | 161,733,481 | 100% | ||
giantroc | 0 | 149,975,524 | 100% | ||
koboldminer | 0 | 149,792,537 | 100% | ||
crustaceanking | 0 | 163,031,061 | 100% | ||
waterelemental | 0 | 149,862,445 | 100% | ||
goblinsorcerer | 0 | 150,049,015 | 100% | ||
ragingimpaler | 0 | 150,571,816 | 100% | ||
animatedcorpse | 0 | 162,777,490 | 100% | ||
spiritforest | 0 | 150,241,377 | 100% | ||
serpentflame | 0 | 150,091,335 | 100% | ||
goblincaptain | 0 | 163,770,323 | 100% | ||
lyannaforest | 0 | 163,365,095 | 100% | ||
divineknight | 0 | 150,206,655 | 100% | ||
feralwarrior | 0 | 150,163,252 | 100% | ||
elementalair | 0 | 163,439,367 | 100% | ||
jestertwisted | 0 | 150,462,532 | 100% | ||
bansheescreaming | 0 | 150,164,243 | 100% | ||
skyselenia | 0 | 150,054,938 | 100% | ||
darknesslord | 0 | 150,131,071 | 100% | ||
lightangel | 0 | 150,535,801 | 100% | ||
naturalyanna | 0 | 150,352,567 | 100% | ||
astormbringer | 0 | 150,164,150 | 100% | ||
giantfrost | 0 | 163,476,830 | 100% | ||
warriorminotaur | 0 | 163,368,316 | 100% | ||
golemalric | 0 | 150,462,440 | 100% | ||
orcelemental | 0 | 162,220,058 | 100% | ||
spiritpriest | 0 | 150,242,794 | 100% | ||
lordjester | 0 | 163,444,102 | 100% | ||
magifirestorm | 0 | 149,722,194 | 100% | ||
muhan | 0 | 149,609,291 | 100% | ||
goodcontentbot2 | 0 | 0 | 12.5% | ||
ond | 0 | 407,987,957 | 90% | ||
smseller | 0 | 68,062,333 | 100% | ||
cpt-sparrow | 0 | 0 | 4.59% | ||
yiobri | 0 | 0 | 12.5% | ||
delegate4upvotes | 0 | 0 | 12.5% | ||
blockcleaner | 0 | 24,129,164,477 | 100% | ||
sctm.winners | 0 | 1,492,071,967 | 100% | ||
steem.leo | 0 | 236,369,904 | 4.59% | ||
cplusplus | 0 | 6,434,277,518 | 100% | ||
yarak-hasan | 0 | 0 | 12.5% | ||
leo.voter | 0 | 199,697,009 | 4.59% | ||
justsoso | 0 | 1,577,443,773 | 100% | ||
soonhai | 0 | 0 | 9% | ||
perrymine | 0 | 93,508,499 | 10% | ||
dcinside | 0 | 667,905,565 | 12.5% | ||
jahid1971 | 0 | 0 | 0.75% | ||
longhash | 0 | 1,448,954,046 | 100% | ||
bilpcoinrecords | 0 | 437,866,189 | 12.5% | ||
tridiner | 0 | 0 | -10% | ||
zzan.upvote | 0 | 0 | 25% | ||
im-ridd | 0 | 13,591,087 | 7.5% | ||
block.token | 0 | 0 | 25% | ||
warmstill | 0 | 0 | 100% | ||
disagio.gang | 0 | 27,024,321 | 7.5% | ||
aceh.point | 0 | 1,921,321,519 | 25% | ||
sexybeach | 0 | 6,538,565,719 | 100% | ||
suckmydick | 0 | 3,146,935,626 | 100% | ||
chromebook | 0 | 1,861,040,787 | 100% | ||
ericandryan | 0 | 14,146,054,119 | 100% | ||
kjinhyun | 0 | 17,401,218,069 | 5% | ||
dev.supporters | 0 | 80,260,618,103 | 10% | ||
hive-156383 | 0 | 380,263,252 | 5% | ||
plato2005 | 0 | 11,273,853,253 | 100% | ||
justyy222 | 0 | 3,087,359,141 | 100% | ||
juddsmith079 | 0 | 256,676,856,592 | 100% | ||
curator-id | 0 | 4,062,547,780 | 25% | ||
sheya | 0 | 7,098,672,708 | 100% | ||
enchanter88 | 0 | 3,532,229,962 | 100% | ||
okoyejoshua | 0 | 5,610,225,683 | 25% | ||
chant | 0 | 2,816,570,357 | 12.5% | ||
alpha-omega | 0 | 2,117,905,029 | 100% | ||
rabumah | 0 | 32,557,945 | 12.5% | ||
deathtox | 0 | 818,896,717 | 25% | ||
thegreatwonder | 0 | 1,760,554 | 12.5% | ||
affable | 0 | 3,796,536,865 | 100% | ||
syei | 0 | 230,039 | 12.5% | ||
izraelinspired | 0 | 70,913,926 | 12.5% | ||
unfamiliar | 0 | 348,932,194 | 100% | ||
motriks | 0 | 23,299,510 | 25% | ||
antoris123 | 0 | 20,497,392 | 12.5% | ||
ldsn001 | 0 | 35,222,837,765 | 50% | ||
chikodi | 0 | 1,999,550,042 | 12.5% | ||
astilem | 0 | 1,873,296,128 | 100% | ||
adrianal | 0 | 0 | 12.5% | ||
blues529 | 0 | 5,088,838,464 | 100% | ||
sebassv | 0 | 1,632,076,518 | 100% | ||
sweetdreamsxo | 0 | 565,940,848 | 100% | ||
lother68 | 0 | 1,231,625,936 | 100% | ||
irsantwin | 0 | 38,292,215,275 | 100% | ||
screenshot-boost | 0 | 1,024,558,212 | 25% | ||
white-bai | 0 | 226,293,963 | 100% | ||
jorden123 | 0 | 229,972,356 | 22% | ||
yusriz4l | 0 | 671,139,081 | 100% | ||
mistrie | 0 | 19,993,250 | 25% | ||
xianlaiyiju | 0 | 73,760,525 | 100% | ||
wiltord | 0 | 423,552,903 | 100% | ||
g66668888 | 0 | 15,811,744,957 | 100% | ||
amr1 | 0 | 1,979,422,836 | 100% |