TheRealSamuel/LeetCodeProblem
0574
1{2 "id": 3209,3 "name": "minimum_number_of_coins_for_fruits",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/minimum-number-of-coins-for-fruits/",6 "date": "2023-11-11 00:00:00",7 "task_description": "You are given an **0-indexed** integer array `prices` where `prices[i]` denotes the number of coins needed to purchase the `(i + 1)th` fruit. The fruit market has the following reward for each fruit: If you purchase the `(i + 1)th` fruit at `prices[i]` coins, you can get any number of the next `i` fruits for free. **Note** that even if you **can** take fruit `j` for free, you can still purchase it for `prices[j - 1]` coins to receive its reward. Return the **minimum** number of coins needed to acquire all the fruits. **Example 1:** **Input:** prices = [3,1,2] **Output:** 4 **Explanation:** Purchase the 1st fruit with `prices[0] = 3` coins, you are allowed to take the 2nd fruit for free. Purchase the 2nd fruit with `prices[1] = 1` coin, you are allowed to take the 3rd fruit for free. Take the 3rd fruit for free. Note that even though you could take the 2nd fruit for free as a reward of buying 1st fruit, you purchase it to receive its reward, which is more optimal. **Example 2:** **Input:** prices = [1,10,1,1] **Output:** 2 **Explanation:** Purchase the 1st fruit with `prices[0] = 1` coin, you are allowed to take the 2nd fruit for free. Take the 2nd fruit for free. Purchase the 3rd fruit for `prices[2] = 1` coin, you are allowed to take the 4th fruit for free. Take the 4th fruit for free. **Example 3:** **Input:** prices = [26,18,6,12,49,7,45,45] **Output:** 39 **Explanation:** Purchase the 1st fruit with `prices[0] = 26` coin, you are allowed to take the 2nd fruit for free. Take the 2nd fruit for free. Purchase the 3rd fruit for `prices[2] = 6` coin, you are allowed to take the 4th, 5th and 6th (the next three) fruits for free. Take the 4th fruit for free. Take the 5th fruit for free. Purchase the 6th fruit with `prices[5] = 7` coin, you are allowed to take the 8th and 9th fruit for free. Take the 7th fruit for free. Take the 8th fruit for free. Note that even though you could take the 6th fruit for free as a reward of buying 3rd fruit, you purchase it to receive its reward, which is more optimal. **Constraints:** `1 <= prices.length <= 1000` `1 <= prices[i] <= 105`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "prices = [3,1,2]",12 "output": "4 "13 },14 {15 "label": "Example 2",16 "input": "prices = [1,10,1,1]",17 "output": "2 "18 },19 {20 "label": "Example 3",21 "input": "prices = [26,18,6,12,49,7,45,45]",22 "output": "39 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 25274,29 21829,30 95346,31 28245,32 24245,33 37803,34 38360,35 16039,36 31802,37 23193,38 33504,39 97219,40 16925,41 70574,42 13560,43 7625,44 82860,45 76280,46 96716,47 73895,48 22692,49 51136,50 87146,51 65163,52 51629,53 44000,54 20919,55 25697,56 77628,57 21836,58 24398,59 54626,60 26704,61 28996,62 75626,63 49812,64 14484,65 90212,66 29445,67 28574,68 66907,69 74570,70 89418,71 32886,72 32293,73 6088,74 55831,75 21697,76 38819,77 74671,78 47965,79 11396,80 66086,81 16298,82 21840,83 85271,84 75761,85 9501,86 95228,87 19405,88 23632,89 24389,90 24377,91 62787,92 96480,93 57008,94 84889,95 54563,96 46663,97 15678,98 50535,99 72823,100 2389,101 77445,102 32480,103 90368,104 15052,105 43885,106 35417,107 24399,108 26527,109 56252,110 53344,111 97174,112 14198,113 55647,114 31911,115 55084,116 97817,117 176,118 59785,119 12706,120 98256,121 70328,122 87691,123 68884,124 52055,125 61581,126 28214,127 80709,128 96084,129 34913,130 19845,131 43427,132 56047,133 91419,134 37292,135 28720,136 18420,137 64021,138 28012,139 57830,140 5738,141 75211,142 45206,143 4045,144 23675,145 12586,146 22254,147 4665,148 27040,149 79391,150 22283,151 46279,152 41200,153 76915,154 1176,155 22144,156 14147,157 24175,158 89960,159 44127,160 44437,161 84993,162 31304,163 87132,164 61776,165 89137,166 50126,167 36772,168 77920,169 65015,170 70168,171 44093,172 43002,173 84834,174 4751,175 69070,176 22323,177 97538,178 21920,179 76721,180 41462,181 86518,182 68262,183 75616,184 4607,185 55684,186 61921,187 93969,188 18161,189 31598,190 3124,191 30911,192 37361,193 68210,194 7329,195 76304,196 3770,197 54397,198 74791,199 92941,200 55638,201 29337,202 59087,203 27593,204 17671,205 66290,206 7105,207 42309,208 91197,209 52966,210 89293,211 51785,212 17079,213 3369,214 72463,215 43418,216 99070,217 5560,218 66924,219 10423,220 8102,221 92488,222 27378,223 18189,224 91738,225 33005,226 32280,227 49365,228 87150,229 49628,230 38591,231 31944,232 40121,233 87860,234 40269,235 56710,236 3281,237 32381,238 92163,239 89701,240 32387,241 3807,242 77778,243 18988,244 48548,245 39641,246 95800,247 5179,248 29904,249 28267,250 63162,251 83210,252 84095,253 52268,254 88162,255 90863,256 93578,257 7550,258 72386,259 47560,260 16251,261 26075,262 5196,263 59010,264 98520,265 25039,266 93383,267 29945,268 10287,269 65817,270 66536,271 76113,272 79093,273 17575,274 61324,275 51883,276 20694,277 60603,278 28450,279 63310,280 73433,281 86161,282 6785,283 57728,284 52602,285 64516,286 85688,287 53199,288 77800,289 17631,290 78309,291 30500,292 51212,293 22004,294 58234,295 7996,296 28086,297 80252,298 15692,299 99887,300 88585,301 94936,302 77129,303 73452,304 76823,305 89339,306 79384,307 79277,308 26511,309 38364,310 74974,311 75977,312 48064,313 7543,314 45588,315 98664,316 73282,317 20401,318 75286,319 87778,320 86337,321 67886,322 8907,323 20380,324 17677,325 69449,326 79567,327 62464,328 41909,329 55384,330 11362,331 14807,332 7294,333 87880,334 96017,335 99971,336 88796,337 10323,338 67695,339 77267,340 51342,341 2682,342 205,343 64755,344 27214,345 65733,346 85496,347 23706,348 88159,349 28288,350 98958,351 76058,352 78709,353 71098,354 54940,355 97467,356 45648,357 21663,358 20507,359 75111,360 78383,361 55692,362 39811,363 20207,364 98747,365 6294,366 59015,367 11362,368 26670,369 49111,370 72097,371 87180,372 34887,373 97415,374 86399,375 93755,376 12391,377 78121,378 49288,379 89879,380 75280,381 77655,382 38577,383 54617,384 31076,385 75623,386 62253,387 29826,388 4761,389 30602,390 22208,391 72349,392 8736,393 34530,394 47544,395 81048,396 39409,397 3121,398 75148,399 71824,400 85852,401 26634,402 22537,403 14791,404 13582,405 32043,406 3,407 14194,408 1509,409 67020,410 27193,411 76831,412 48821,413 5791,414 39372,415 87427,416 3266,417 31240,418 85126,419 44559,420 74066,421 54239,422 34138,423 93964,424 63328,425 73840,426 75331,427 12796,428 83605,429 38516,430 87981,431 25519,432 69524,433 24068,434 58527,435 14034,436 97772,437 75690,438 97292,439 12094,440 18063,441 57660,442 59622,443 15009,444 9947,445 47798,446 14709,447 56415,448 8481,449 78315,450 58717,451 29398,452 38564,453 45851,454 12726,455 1148,456 61644,457 62166,458 69410,459 1682,460 28420,461 40121,462 77581,463 98494,464 82847,465 14444,466 84529,467 16546,468 3163,469 55333,470 12656,471 1980,472 52693,473 8546,474 30411,475 77251,476 48376,477 77286,478 77690,479 75453,480 95132,481 79815,482 313,483 11257,484 68173,485 69882,486 82518,487 4405,488 90998,489 85976,490 55016,491 70891,492 87410,493 87579,494 332,495 9433,496 49780,497 77044,498 63658,499 75626,500 97957,501 34844,502 25115,503 12789,504 57294,505 23840,506 69431,507 36106,508 22662,509 10300,510 61423,511 44506,512 93224,513 53515,514 90565,515 27916,516 90476,517 63726,518 33299,519 43574520 ],521 "output": 125524522 },523 {524 "input": [525 87456,526 62878,527 2902,528 19684,529 18472,530 71532,531 47090,532 95104,533 93715,534 7242,535 12971,536 42860,537 52919,538 24131,539 30584,540 70208,541 97914,542 47047,543 90047,544 47793,545 53991,546 59800,547 41309,548 66673,549 58872,550 5251,551 11960,552 56641,553 62105,554 78866,555 64470,556 61227,557 17719,558 77876,559 68947,560 20734,561 66117,562 45917,563 68884,564 65689,565 38691,566 29680,567 96821,568 27581,569 62125,570 59353,571 64541,572 49569,573 9569,574 76300,575 60736,576 65234,577 81941,578 98028,579 64952,580 65082,581 91370,582 92902,583 88308,584 74634,585 22593,586 1424,587 83187,588 95049,589 54761,590 31556,591 85312,592 30480,593 47625,594 37928,595 12594,596 50370,597 91529,598 93968,599 75410,600 25030,601 87006,602 10469,603 72915,604 9229,605 23726,606 9072,607 84395,608 10898,609 81428,610 41910,611 69049,612 90322,613 41725,614 23712,615 56668,616 95116,617 85601,618 19800,619 37019,620 45850,621 88633,622 99940,623 11015,624 93824,625 17633,626 41577,627 74372,628 79513,629 32894,630 52410,631 53586,632 88069,633 72276,634 20595,635 57818,636 20651,637 23237,638 13247,639 22506,640 96935,641 38734,642 19604,643 67796,644 20404,645 59826,646 10987,647 67747,648 54172,649 41049,650 55585,651 99181,652 3307,653 36320,654 23217,655 38570,656 24422,657 89438,658 74373,659 48552,660 77461,661 27869,662 85999,663 23599,664 63626,665 43067,666 80563,667 10227,668 735,669 56578,670 43862,671 6553,672 18750,673 30742,674 31466,675 29422,676 31765,677 7203,678 29625,679 57602,680 97387,681 61988,682 58919,683 84463,684 80096,685 97805,686 6694,687 3299,688 93698,689 68681,690 97520,691 14321,692 24095,693 2209,694 87482,695 28490,696 14591,697 70301,698 91029,699 90807,700 74788,701 68482,702 37611,703 15297,704 62563,705 59487,706 47095,707 67264,708 63078,709 40520,710 33555,711 18124,712 1678,713 88234,714 13958,715 27021,716 13544,717 57608,718 81353,719 81785,720 64860,721 7708,722 9143,723 9366,724 76781,725 51827,726 87629,727 40455,728 84072,729 7224,730 49524,731 18016,732 68911,733 71537,734 7207,735 23979,736 28366,737 80429,738 17705,739 17657,740 20278,741 55111,742 91874,743 99647,744 82400,745 66899,746 40858,747 87910,748 54519,749 33181,750 15907,751 26509,752 1702,753 5190,754 14305,755 96057,756 89065,757 65316,758 37989,759 53407,760 79703,761 37494,762 46065,763 65536,764 96393,765 36447,766 45812,767 88829,768 49190,769 49430,770 54540,771 96090,772 55284,773 63598,774 63059,775 69078,776 27801,777 66994,778 29261,779 60866,780 70611,781 6747,782 38134,783 86922,784 40672,785 19322,786 51545,787 35953,788 86611,789 5907,790 60819,791 44182,792 7388,793 76210,794 73752,795 18672,796 13205,797 36423,798 10400,799 62260,800 62690,801 98658,802 77575,803 50891,804 55349,805 16424,806 1618,807 51165,808 38135,809 35194,810 38412,811 22192,812 96906,813 50318,814 19300,815 41411,816 71158,817 638,818 57903,819 60659,820 329,821 41891,822 97441,823 18699,824 93087,825 56300,826 59594,827 74651,828 4680,829 21505,830 37996,831 96514,832 84878,833 21974,834 47520,835 301,836 28408,837 70978,838 48326,839 22243,840 7952,841 88939,842 36656,843 70636,844 57347,845 32199,846 89057,847 67554,848 53754,849 57646,850 37996,851 66181,852 53654,853 85595,854 88692,855 64331,856 91864,857 10914,858 82070,859 60825,860 1927,861 92361,862 66082,863 77494,864 94377,865 96529,866 88807,867 51196,868 55666,869 90825,870 77312,871 2279,872 32783,873 68228,874 19170,875 36062,876 38519,877 53159,878 17745,879 33858,880 10841,881 27185,882 76894,883 36642,884 73917,885 10228,886 7893,887 37231,888 13274,889 61549,890 43292,891 59764,892 79262,893 6777,894 64665,895 91246,896 43223,897 43330,898 37727,899 38088,900 68627,901 78509,902 24068,903 53926,904 57526,905 45247,906 86166,907 13774,908 11886,909 82584,910 78138,911 2070,912 20345,913 19377,914 74370,915 94565,916 8802,917 9934,918 40092,919 19034,920 43863,921 63531,922 74324,923 90720,924 84616,925 13947,926 18953,927 10971,928 40124,929 47764,930 21512,931 51855,932 93163,933 93537,934 48420,935 58795,936 70793,937 15406,938 64185,939 10269,940 97514,941 94056,942 6294,943 81886,944 62820,945 69194,946 4396,947 82523,948 19813,949 83426,950 94755,951 77451,952 33750,953 7196,954 52125,955 49081,956 4892,957 53507,958 82658,959 19517,960 30730,961 60257,962 82177,963 31750,964 9876,965 40391,966 70406,967 32192,968 61600,969 5132,970 46579,971 89452,972 40648,973 96364,974 53534,975 71857,976 39507,977 905,978 8471,979 13111,980 12125,981 14147,982 75894,983 42053,984 62717,985 36940,986 50594,987 50901,988 45227,989 26669,990 2633,991 41612,992 65779,993 17592,994 37429,995 24384,996 18717,997 14292,998 30803,999 40041,1000 95208,1001 91884,1002 12527,1003 72464,1004 80393,1005 988,1006 18941,1007 34197,1008 14541,1009 1709,1010 42299,1011 46355,1012 41995,1013 83214,1014 23682,1015 50805,1016 86339,1017 36149,1018 75794,1019 37412,1020 19184,1021 21949,1022 700,1023 66087,1024 49442,1025 96729,1026 94830,1027 65052,1028 68093,1029 43150,1030 19919,1031 9353,1032 12387,1033 44944,1034 75125,1035 82166,1036 85707,1037 91538,1038 39421,1039 79330,1040 48831,1041 39495,1042 44036,1043 21466,1044 41455,1045 52815,1046 43212,1047 72804,1048 58376,1049 68281,1050 31411,1051 20636,1052 57684,1053 53185,1054 15382,1055 73383,1056 64746,1057 44022,1058 47497,1059 76274,1060 96038,1061 54176,1062 72869,1063 58876,1064 38387,1065 11204,1066 40250,1067 47433,1068 83584,1069 22167,1070 25364,1071 90094,1072 19675,1073 84728,1074 30636,1075 89583,1076 6244,1077 70605,1078 81838,1079 73503,1080 46830,1081 70779,1082 80694,1083 40773,1084 41043,1085 7034,1086 84806,1087 66315,1088 45586,1089 60034,1090 10368,1091 36218,1092 83697,1093 88771,1094 34382,1095 78079,1096 14202,1097 13149,1098 15319,1099 27466,1100 40632,1101 61016,1102 69860,1103 72756,1104 42894,1105 95686,1106 8765,1107 312221108 ],1109 "output": 1667491110 },1111 {1112 "input": [1113 51869,1114 76872,1115 71438,1116 92190,1117 9550,1118 89065,1119 40629,1120 41068,1121 57474,1122 45987,1123 35992,1124 47570,1125 10130,1126 12426,1127 52908,1128 43666,1129 48032,1130 36253,1131 21873,1132 44893,1133 227,1134 11500,1135 85939,1136 78161,1137 34907,1138 84069,1139 10218,1140 27662,1141 35236,1142 89218,1143 22436,1144 60675,1145 11664,1146 83328,1147 88050,1148 6105,1149 17949,1150 31568,1151 8097,1152 7233,1153 50869,1154 82415,1155 63501,1156 90416,1157 32986,1158 85801,1159 97821,1160 48386,1161 20538,1162 2408,1163 32049,1164 86059,1165 15230,1166 15944,1167 98583,1168 83603,1169 74872,1170 71531,1171 13026,1172 64050,1173 48867,1174 72239,1175 23800,1176 14169,1177 23551,1178 10798,1179 23069,1180 76516,1181 68101,1182 79800,1183 32657,1184 29829,1185 25147,1186 17923,1187 38690,1188 8792,1189 96986,1190 91902,1191 94129,1192 73297,1193 72497,1194 60846,1195 1753,1196 99925,1197 96434,1198 74552,1199 76583,1200 31658,