TheRealSamuel/LeetCodeProblem
0561
1{2 "id": 2670,3 "name": "make_k_subarray_sums_equal",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/make-k-subarray-sums-equal/",6 "date": "1679097600000",7 "task_description": "You are given a **0-indexed** integer array `arr` and an integer `k`. The array `arr` is circular. In other words, the first element of the array is the next element of the last element, and the last element of the array is the previous element of the first element. You can do the following operation any number of times: Pick any element from `arr` and increase or decrease it by `1`. Return _the minimum number of operations such that the sum of each **subarray** of length _`k`_ is equal_. A **subarray** is a contiguous part of the array. **Example 1:** ``` **Input:** arr = [1,4,1,3], k = 2 **Output:** 1 **Explanation:** we can do one operation on index 1 to make its value equal to 3. The array after the operation is [1,3,1,3] - Subarray starts at index 0 is [1, 3], and its sum is 4 - Subarray starts at index 1 is [3, 1], and its sum is 4 - Subarray starts at index 2 is [1, 3], and its sum is 4 - Subarray starts at index 3 is [3, 1], and its sum is 4 ``` **Example 2:** ``` **Input:** arr = [2,5,5,7], k = 3 **Output:** 5 **Explanation:** we can do three operations on index 0 to make its value equal to 5 and two operations on index 3 to make its value equal to 5. The array after the operations is [5,5,5,5] - Subarray starts at index 0 is [5, 5, 5], and its sum is 15 - Subarray starts at index 1 is [5, 5, 5], and its sum is 15 - Subarray starts at index 2 is [5, 5, 5], and its sum is 15 - Subarray starts at index 3 is [5, 5, 5], and its sum is 15 ``` **Constraints:** `1 <= k <= arr.length <= 105` `1 <= arr[i] <= 109`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "arr = [1,4,1,3], k = 2",12 "output": "1 "13 },14 {15 "label": "Example 2",16 "input": "arr = [2,5,5,7], k = 3",17 "output": "5 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 [24 411440961,25 479228108,26 846536696,27 213956621,28 470440189,29 934283870,30 816468685,31 128150573,32 574634398,33 659692438,34 79758305,35 563138399,36 686036189,37 665529921,38 862521737,39 481410313,40 839015142,41 249292132,42 288804789,43 307705039,44 446331679,45 354111445,46 917646518,47 962828142,48 333103734,49 908012949,50 677380949,51 881051872,52 460929623,53 782392800,54 419195114,55 223923727,56 551525158,57 872154567,58 135817892,59 621664472,60 353233727,61 31824251,62 981065410,63 147304333,64 17585577,65 746889299,66 862255106,67 73008661,68 46262541,69 135792575,70 935110240,71 387764398,72 466996699,73 322706743,74 187960783,75 62287312,76 961828456,77 547630691,78 539689560,79 765308759,80 832576711,81 540537192,82 285506088,83 437828317,84 728602027,85 59256060,86 265966843,87 957112996,88 395985823,89 454148576,90 769932206,91 434840317,92 626955623,93 722304152,94 568567840,95 939646556,96 536578703,97 918534422,98 420248102,99 24023376,100 286300182,101 273565932,102 633345447,103 237533964,104 19548965,105 67980915,106 486668873,107 179749426,108 710372310,109 857286861,110 531306236,111 217553011,112 441238863,113 385834280,114 612711373,115 285670325,116 89878076,117 970894336,118 440917621,119 190156638,120 984858046,121 995129067,122 818979732,123 104563954,124 927968761,125 672454647,126 783779886,127 339897130,128 126840412,129 552384557,130 596098398,131 176032313,132 554197604,133 187411113,134 790813264,135 274173072,136 825520585,137 694792095,138 120928078,139 876997342,140 84062240,141 686574622,142 822794220,143 155667759,144 268743546,145 895861465,146 646878505,147 21243771,148 968168737,149 566517603,150 446050877,151 644865734,152 131051580,153 575986906,154 774358671,155 482333577,156 14040565,157 12265169,158 290850457,159 189492849,160 431697112,161 342531939,162 695659154,163 532601470,164 672633286,165 242326115,166 56289760,167 198108648,168 347050247,169 619645252,170 592819676,171 680288137,172 752472839,173 428132254,174 926400391,175 771958312,176 914197093,177 546374340,178 982644798,179 45115623,180 722389028,181 122577488,182 372212401,183 987155086,184 45797650,185 70467832,186 543270055,187 768226971,188 563795039,189 618335520,190 166141660,191 406014741,192 199122076,193 679024672,194 306584986,195 477067751,196 313075592,197 74932157,198 872769544,199 467748164,200 74224912,201 12174610,202 587003510,203 612110732,204 595100349,205 703608841,206 238960736,207 427502681,208 278412755,209 831127173,210 746331197,211 152746269,212 753043711,213 420226680,214 936805781,215 72194759,216 786865874,217 466622456,218 391745764,219 6698817,220 166143953,221 976228096,222 278039841,223 15158032,224 379135303,225 140621147,226 619839114,227 95986429,228 686159841,229 486076036,230 184821594,231 31851974,232 298442084,233 833028855,234 139318079,235 282987553,236 962990068,237 847617703,238 859808600,239 356552410,240 870061725,241 878475029,242 455288489,243 398201414,244 752317002,245 563701784,246 944692142,247 673369820,248 130568435,249 536344089,250 106894423,251 216694599,252 286950831,253 680150024,254 470831976,255 364806102,256 552884862,257 476676178,258 1626818,259 550083272,260 679081181,261 477289138,262 982206264,263 936954599,264 549986676,265 973646835,266 815595931,267 860729001,268 394473182,269 175252248,270 927213428,271 501410554,272 25642230,273 6152236,274 615584871,275 200019792,276 610002867,277 374888239,278 746725412,279 358820088,280 416301399,281 947662203,282 546362674,283 854531475,284 787659243,285 769461637,286 898732183,287 597121970,288 861830350,289 635788670,290 946625619,291 326889503,292 665044048,293 710873419,294 568874218,295 391089180,296 570024849,297 233174876,298 641427240,299 678615219,300 130713275,301 247869982,302 576959077,303 474472073,304 852583665,305 783333704,306 576702618,307 587410566,308 174940696,309 904424717,310 211923305,311 715197497,312 606620470,313 213029872,314 935890571,315 208233288,316 133930357,317 269043243,318 443137695,319 532680335,320 285690854,321 24518569,322 107134390,323 275734675,324 579860100,325 188455138,326 574414796,327 618951458,328 454247506,329 679479893,330 506261949,331 768108403,332 260679689,333 644700545,334 528329237,335 582363907,336 787890473,337 341990083,338 176182176,339 212324967,340 993208708,341 83917574,342 107207810,343 821957922,344 678605436,345 923866901,346 655452017,347 663297817,348 577424582,349 363435038,350 391069651,351 701906219,352 962386337,353 538956780,354 197939812,355 26521837,356 966717119,357 804242964,358 79884982,359 861887663,360 33756559,361 953352641,362 339709398,363 149134852,364 415893964,365 44829955,366 926923820,367 888602183,368 723261807,369 409989756,370 352744414,371 127483033,372 519478813,373 171972553,374 899430942,375 823409443,376 59883104,377 226198984,378 363140451,379 57440029,380 232350703,381 185817193,382 482461433,383 653966308,384 405085111,385 641221489,386 97601138,387 659214003,388 30829699,389 651252931,390 456330970,391 590766322,392 702309276,393 806425889,394 603017229,395 416084199,396 305549586,397 989865352,398 775700388,399 880579796,400 948026252,401 60638483,402 620746150,403 190225466,404 98390270,405 747443604,406 43821425,407 592397183,408 281864415,409 524023054,410 872715386,411 596670892,412 255412709,413 447187389,414 907253462,415 69557782,416 593032428,417 975462436,418 693500776,419 163826138,420 441106965,421 579817014,422 897726023,423 775907845,424 881053393,425 216784316,426 850770236,427 736912373,428 714299511,429 255274508,430 585749111,431 235695518,432 874507851,433 72708321,434 177155623,435 535582507,436 519381564,437 121670950,438 947947582,439 600131374,440 795366962,441 243888894,442 105305485,443 859920186,444 822757367,445 637328909,446 954697532,447 520030336,448 73289802,449 485172757,450 320867907,451 867615825,452 514418960,453 892459396,454 924225750,455 831049416,456 766979196,457 907575258,458 339918142,459 17290942,460 773783162,461 939423480,462 723972779,463 770813101,464 814047546,465 117241439,466 56182887,467 802862833,468 145796885,469 212954607,470 70664251,471 619535490,472 323191491,473 479103640,474 558532746,475 327410600,476 558502590,477 931867550,478 15737519,479 472120462,480 823686703,481 971527004,482 506453277,483 536483711,484 739479919,485 189237457,486 116183162,487 948523751,488 516019115,489 789355453,490 426841436,491 798976137,492 470228492,493 841723856,494 69197200,495 608686238,496 674517798,497 104288236,498 518203123,499 414434930,500 722738632,501 250905486,502 531800733,503 461952015,504 506622256,505 49208180,506 2622081,507 980190774,508 878340739,509 367790125,510 352577320,511 358134531,512 863019754,513 113946868,514 352889547,515 336570977,516 218456871,517 218133863,518 48642062,519 98790093,520 26351692,521 331518183,522 682522211,523 520807549,524 780535041,525 464749698,526 184861610,527 513588249,528 1501173,529 973871425,530 307313802,531 43222119,532 352644571,533 591862699,534 855293459,535 89630539,536 960821582,537 198827553,538 935777437,539 783883772,540 953207177,541 166245923,542 259621220,543 329060048,544 661048108,545 309347781,546 370819311,547 246972652,548 897167426,549 432430735,550 515534868,551 51740856,552 198764303,553 164200238,554 274097608,555 132683763,556 382879041,557 150336180,558 612739325,559 998999088,560 291758365,561 796501452,562 451919634,563 731130610,564 592883723,565 77174566,566 192584847,567 768611121,568 598395691,569 241406080,570 981174537,571 135905725,572 925490638,573 406034827,574 843660964,575 772148529,576 374056142,577 3524859,578 778181322,579 607840141,580 213186611,581 340603420,582 861459506,583 944768233,584 380210002,585 461894600,586 692428773,587 430676938,588 546099657,589 293245147,590 503336833,591 956811125,592 68991680,593 847829901,594 170987306,595 352809302,596 740962208,597 961122259,598 507018565,599 142133847,600 804783693,601 572230871,602 322257471,603 58795786,604 730410820,605 30322200,606 762206543,607 341313383,608 574773442,609 385512449,610 484365975,611 350664582,612 521677305,613 690291515,614 330941985,615 604351194,616 989383495,617 473719063,618 548366242,619 69306172,620 244567585,621 214913647,622 661382155,623 553527092,624 867736222,625 898930135,626 500749515,627 466734525,628 3405609,629 440519282,630 584024350,631 83458685,632 496727167,633 821287665,634 129873241,635 576145317,636 893884878,637 486989372,638 859053384,639 256255385,640 369670507,641 349461593,642 519411579,643 397384300,644 263401802,645 61931949,646 732954092,647 608826910,648 485483901,649 81638228,650 168895314,651 550258556,652 904324538,653 904999854,654 906393530,655 409810068,656 241238785,657 987625565,658 642986110,659 34043797,660 16571610,661 843634769,662 2584287,663 770482042,664 107598752,665 879244688,666 477497274,667 201664757,668 322454183,669 491275445,670 70468187,671 584280610,672 860615442,673 394142273,674 534760472,675 346886771,676 117402434,677 830703442,678 433088025,679 501403275,680 13632422,681 948643201,682 720266656,683 400174016,684 851119303,685 13016773,686 286003683,687 407587362,688 235928068,689 951605022,690 570913217,691 683826540,692 376618000,693 275438825,694 559165875,695 205919076,696 152614737,697 978135548,698 640332318,699 421120589,700 265523534,701 76170172,702 697301634,703 676820502,704 702326500,705 273523132,706 730328258,707 737685291,708 954016197,709 875656361,710 250019215,711 125837497,712 472251960,713 595414622,714 698886744,715 91748064,716 751735012,717 641547618,718 497883423,719 249583172,720 775084501,721 110020937,722 186701741,723 114533253,724 58484844,725 240537108,726 493947804,727 997689668,728 63120075,729 241513620,730 638905293,731 772528490,732 66474915,733 271911251,734 354332159,735 898980166,736 519363490,737 544706534,738 629192369,739 860529639,740 818361495,741 301369890,742 508481630,743 911947314,744 619875444,745 491247397,746 468385062,747 484892345,748 744024341,749 492722995,750 907155466,751 443521530,752 575020033,753 832769669,754 24558334,755 510983921,756 417244787,757 724510171,758 872189254,759 310858609,760 842369675,761 107692487,762 753655557,763 269038386,764 270571059,765 666564549,766 180159135,767 99824096,768 759146014,769 667114344,770 635583828,771 587770388,772 539569407,773 942007914,774 721994015,775 277533542,776 424252243,777 895458692,778 200702632,779 251239081,780 725939735,781 527861353,782 481397336,783 363823328,784 857603325,785 375027886,786 471550781,787 312003884,788 368361742,789 521495886,790 897270666,791 538498640,792 664260857,793 963077367,794 715698931,795 103038723,796 370362563,797 330075203,798 5142864,799 835525880,800 95258768,801 685454933,802 332458853,803 704698274,804 591470750,805 724601440,806 689178188,807 870746839,808 582768625,809 945015310,810 472248780,811 186440349,812 462107119,813 65225333,814 438217211,815 359212894,816 59997095,817 492569052,818 635966289,819 262166333,820 299622431,821 28479094,822 555521906,823 433186053,824 114565728,825 409663330,826 438093782,827 339265476,828 626272942,829 892879188,830 395624515,831 362183670,832 885660557,833 170752855,834 173192117,835 999420761,836 577325702,837 193215941,838 836881653,839 128075188,840 4960570,841 595426591,842 708732823,843 223526966,844 911502008,845 360164603,846 641730441,847 337161594,848 525053772,849 562701661,850 805400209,851 463986398,852 666361276,853 961341542,854 989917307,855 617962872,856 749969092,857 240713867,858 222600583,859 186057539,860 762552186,861 137174788,862 899429739,863 67343258,864 115851677,865 805536081,866 206193835,867 649455006,868 418984225,869 406372781,870 997679134,871 627551414,872 898699371,873 699263157,874 645975126,875 851023515,876 934034879,877 536909623,878 30169690,879 647279900,880 66949236,881 158784031,882 133472230,883 438291896,884 307596392,885 938071760,886 294139932,887 928875626,888 787134064,889 559468443,890 174916272,891 318468744,892 883558331,893 364754329,894 589298445,895 254267584,896 514710521,897 956374326,898 448082387,899 177689787,900 508574274,901 176262630,902 661606651,903 729501195,904 964466975,905 582875062,906 249813596,907 615246205,908 461358298,909 691872609,910 31636528,911 608960386,912 615010228,913 204032299,914 285009759,915 619660031,916 884382459,917 170980864,918 449744588,919 748675087,920 335692017,921 373449744,922 545133940,923 705370511,924 538192808,925 255717663,926 284261351,927 185989412,928 607322661,929 444013208,930 529256403,931 52398032,932 324196177,933 447647146,934 599112701,935 108070355,936 379075405,937 840857128,938 765815028,939 181209043,940 47106782,941 606526800,942 364922560,943 602208379,944 404754111,945 658232061,946 507457071,947 35561974,948 745072381,949 665446727,950 624435580,951 902985985,952 554942377,953 92722119,954 489569642,955 268522098,956 265591319,957 144531424,958 242692738,959 961203935,960 156923920,961 924786023,962 213682065,963 694389484,964 767909119,965 850862120,966 155694968,967 686887102,968 742966963,969 548884899,970 231100067,971 889900267,972 334875652,973 1340482,974 770040954,975 511347189,976 6901754,977 346512666,978 504684297,979 50134256,980 285427015,981 937166999,982 680961708,983 428432138,984 602197105,985 398954939,986 208651287,987 867533139,988 367696322,989 214302738,990 741561969,991 926630044,992 687385718,993 424941910,994 417836104,995 156863801,996 296807872,997 242918234,998 123430565,999 700319331,1000 285227381,1001 121236011,1002 868420892,1003 944411645,1004 124499555,1005 456644648,1006 227152950,1007 608987962,1008 235783233,1009 757317257,1010 125613814,1011 235474057,1012 659298290,1013 763873241,1014 242163008,1015 814414699,1016 306049999,1017 218278472,1018 536273376,1019 422503438,1020 263712950,1021 487183460,1022 824504463,1023 502713740,1024 808250124,1025 795526049,1026 158726329,1027 422288261,1028 925182101,1029 472660037,1030 171373062,1031 911109881,1032 455962917,1033 463734694,1034 396433595,1035 402528698,1036 625583704,1037 477062730,1038 451977912,1039 169792895,1040 194564871,1041 511852516,1042 519612391,1043 865349780,1044 984429653,1045 682800746,1046 321244569,1047 728493337,1048 97692115,1049 393154648,1050 666899328,1051 400829530,1052 780200741,1053 924437085,1054 12725956,1055 941893160,1056 929579052,1057 793474147,1058 583027416,1059 232375075,1060 660706804,1061 157383937,1062 241897451,1063 147510837,1064 798642072,1065 317754538,1066 398782194,1067 620196064,1068 756279926,1069 271307327,1070 873164355,1071 717614452,1072 396815730,1073 735063024,1074 534205724,1075 304163692,1076 757095919,1077 344487066,1078 818700967,1079 994412210,1080 876455615,1081 835195986,1082 243406647,1083 292444142,1084 754981866,1085 228408724,1086 497969836,1087 925808364,1088 620637197,1089 999300308,1090 732581752,1091 118811375,1092 239013886,1093 349488870,1094 891069732,1095 328781827,1096 338306387,1097 527417621,1098 556618167,1099 152895540,1100 585020087,1101 217922062,1102 298885059,1103 573356994,1104 228836050,1105 98843916,1106 958815741,1107 231438283,1108 716693124,1109 629149901,1110 870746521,1111 322823020,1112 776489881,1113 322434932,1114 921801487,1115 391508756,1116 322711160,1117 905302766,1118 120888706,1119 672086657,1120 455669394,1121 975468466,1122 834535579,1123 1806321,1124 904037306,1125 266918337,1126 563799199,1127 211547578,1128 4395985,1129 989799300,1130 307725121,1131 333075852,1132 253014978,1133 43214106,1134 275913413,1135 886960596,1136 644549773,1137 761786026,1138 699227511,1139 630066058,1140 220125502,1141 743199455,1142 530854934,1143 175829204,1144 583254123,1145 543446228,1146 872214639,1147 764858809,1148 804952436,1149 768037522,1150 382616551,1151 220040494,1152 281092076,1153 220453048,1154 444509953,1155 789493672,1156 471086301,1157 562844538,1158 653155510,1159 428520525,1160 744436418,1161 396947170,1162 376886981,1163 981400677,1164 245671546,1165 520167730,1166 820496245,1167 182623219,1168 814343336,1169 659678480,1170 891803433,1171 139756004,1172 194251118,1173 952389792,1174 625324858,1175 993582486,1176 191962477,1177 503596309,1178 844287095,1179 255743285,1180 39275198,1181 973089497,1182 28362435,1183 610637262,1184 777967753,1185 9050354,1186 673659440,1187 349039666,1188 392053687,1189 242866186,1190 707768667,1191 608210082,1192 952128061,1193 422054420,1194 591284004,1195 513389854,1196 478592705,1197 819165905,1198 156921956,1199 673254710,1200 49618286,