TheRealSamuel/LeetCodeProblem
0564
1{2 "id": 3364,3 "name": "minimum_sum_of_values_by_dividing_array",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/minimum-sum-of-values-by-dividing-array/",6 "date": "2024-04-07 00:00:00",7 "task_description": "You are given two arrays `nums` and `andValues` of length `n` and `m` respectively. The **value** of an array is equal to the **last** element of that array. You have to divide `nums` into `m` **disjoint contiguous** subarrays such that for the `ith` subarray `[li, ri]`, the bitwise `AND` of the subarray elements is equal to `andValues[i]`, in other words, `nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i]` for all `1 <= i <= m`, where `&` represents the bitwise `AND` operator. Return _the **minimum** possible sum of the **values** of the _`m`_ subarrays _`nums`_ is divided into_. _If it is not possible to divide _`nums`_ into _`m`_ subarrays satisfying these conditions, return_ `-1`. **Example 1:** **Input:** nums = [1,4,3,3,2], andValues = [0,3,3,2] **Output:** 12 **Explanation:** The only possible way to divide `nums` is: `[1,4]` as `1 & 4 == 0`. `[3]` as the bitwise `AND` of a single element subarray is that element itself. `[3]` as the bitwise `AND` of a single element subarray is that element itself. `[2]` as the bitwise `AND` of a single element subarray is that element itself. The sum of the values for these subarrays is `4 + 3 + 3 + 2 = 12`. **Example 2:** **Input:** nums = [2,3,5,7,7,7,5], andValues = [0,7,5] **Output:** 17 **Explanation:** There are three ways to divide `nums`: `[[2,3,5],[7,7,7],[5]]` with the sum of the values `5 + 7 + 5 == 17`. `[[2,3,5,7],[7,7],[5]]` with the sum of the values `7 + 7 + 5 == 19`. `[[2,3,5,7,7],[7],[5]]` with the sum of the values `7 + 7 + 5 == 19`. The minimum possible sum of the values is `17`. **Example 3:** **Input:** nums = [1,2,3,4], andValues = [2] **Output:** -1 **Explanation:** The bitwise `AND` of the entire array `nums` is `0`. As there is no possible way to divide `nums` into a single subarray to have the bitwise `AND` of elements `2`, return `-1`. **Constraints:** `1 <= n == nums.length <= 104` `1 <= m == andValues.length <= min(n, 10)` `1 <= nums[i] < 105` `0 <= andValues[j] < 105`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [1,4,3,3,2], andValues = [0,3,3,2]",12 "output": "12 "13 },14 {15 "label": "Example 2",16 "input": "nums = [2,3,5,7,7,7,5], andValues = [0,7,5]",17 "output": "17 "18 },19 {20 "label": "Example 3",21 "input": "nums = [1,2,3,4], andValues = [2]",22 "output": "-1 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 18,30 81,31 4,32 5,33 2,34 87,35 8,36 23,37 95,38 74,39 19,40 87,41 18,42 43,43 91,44 22,45 22,46 16,47 23,48 70,49 15,50 95,51 45,52 15,53 22,54 49,55 35,56 2,57 53,58 47,59 89,60 27,61 77,62 14,63 23,64 4,65 1,66 52,67 29,68 66,69 22,70 34,71 25,72 35,73 22,74 24,75 70,76 22,77 6,78 18,79 98,80 30,81 48,82 97,83 95,84 85,85 68,86 41,87 60,88 33,89 67,90 7,91 100,92 95,93 29,94 16,95 80,96 43,97 74,98 47,99 28,100 50,101 88,102 37,103 22,104 4,105 69,106 61,107 91,108 39,109 97,110 54,111 93,112 46,113 99,114 3,115 78,116 57,117 102,118 41,119 62,120 89,121 84,122 8,123 57,124 77,125 73,126 21,127 98,128 63,129 31,130 65,131 49,132 21,133 44,134 49,135 87,136 66,137 55,138 9,139 37,140 81,141 37,142 18,143 96,144 53,145 104,146 23,147 90,148 28,149 74,150 84,151 3,152 71,153 42,154 24,155 58,156 79,157 101,158 4,159 98,160 92,161 83,162 33,163 32,164 37,165 100,166 80,167 49,168 75,169 81,170 73,171 62,172 24,173 82,174 80,175 100,176 27,177 50,178 79,179 62,180 69,181 56,182 92,183 27,184 20,185 59,186 84,187 99,188 59,189 48,190 19,191 28,192 72,193 34,194 37,195 20,196 39,197 81,198 36,199 89,200 83,201 35,202 71,203 12,204 47,205 51,206 70,207 40,208 27,209 66,210 59,211 96,212 89,213 95,214 45,215 73,216 64,217 5,218 33,219 52,220 90,221 15,222 10,223 86,224 4,225 18,226 10,227 90,228 59,229 48,230 101,231 19,232 29,233 71,234 42,235 84,236 52,237 84,238 17,239 48,240 103,241 94,242 57,243 19,244 85,245 51,246 25,247 70,248 45,249 91,250 49,251 27,252 7,253 102,254 54,255 75,256 62,257 93,258 7,259 82,260 89,261 85,262 47,263 87,264 47,265 6,266 17,267 17,268 45,269 10,270 22,271 35,272 77,273 25,274 62,275 8,276 39,277 100,278 54,279 74,280 62,281 25,282 82,283 89,284 99,285 54,286 84,287 79,288 41,289 70,290 84,291 77,292 63,293 93,294 30,295 60,296 100,297 3,298 2,299 100,300 40,301 88,302 9,303 52,304 43,305 65,306 77,307 22,308 18,309 74,310 45,311 81,312 13,313 23,314 32,315 40,316 97,317 11,318 58,319 34,320 52,321 51,322 12,323 24,324 81,325 19,326 87,327 28,328 70,329 28,330 83,331 45,332 27,333 27,334 22,335 42,336 102,337 26,338 102,339 92,340 81,341 90,342 27,343 67,344 59,345 35,346 94,347 89,348 28,349 50,350 44,351 91,352 16,353 52,354 1,355 83,356 46,357 14,358 91,359 80,360 83,361 42,362 63,363 49,364 15,365 37,366 30,367 11,368 30,369 92,370 95,371 11,372 72,373 2,374 22,375 26,376 98,377 58,378 89,379 58,380 91,381 39,382 44,383 72,384 42,385 97,386 76,387 9,388 73,389 32,390 4,391 49,392 65,393 30,394 58,395 25,396 54,397 47,398 80,399 86,400 43,401 38,402 69,403 69,404 51,405 45,406 59,407 99,408 76,409 15,410 40,411 64,412 28,413 84,414 13,415 72,416 46,417 87,418 85,419 48,420 34,421 92,422 76,423 61,424 32,425 40,426 26,427 78,428 16,429 21,430 93,431 101,432 20,433 85,434 34,435 16,436 38,437 13,438 13,439 80,440 10,441 54,442 59,443 51,444 66,445 73,446 77,447 90,448 55,449 63,450 8,451 41,452 30,453 6,454 25,455 15,456 83,457 68,458 101,459 89,460 102,461 103,462 91,463 16,464 97,465 52,466 26,467 89,468 104,469 92,470 17,471 72,472 102,473 79,474 4,475 57,476 98,477 84,478 1,479 88,480 85,481 62,482 67,483 70,484 18,485 65,486 84,487 63,488 21,489 58,490 22,491 6,492 14,493 33,494 10,495 52,496 49,497 94,498 55,499 4,500 27,501 18,502 49,503 93,504 8,505 80,506 3,507 32,508 98,509 49,510 20,511 54,512 59,513 16,514 54,515 87,516 66,517 8,518 2,519 12,520 16,521 6,522 102,523 67,524 8,525 8,526 52,527 13,528 104,529 84,530 78,531 21,532 28,533 43,534 52,535 52,536 88,537 100,538 73,539 10,540 101,541 58,542 102,543 76,544 81,545 32,546 24,547 101,548 84,549 99,550 103,551 66,552 23,553 15,554 29,555 32,556 26,557 67,558 37,559 101,560 66,561 23,562 50,563 16,564 19,565 5,566 17,567 33,568 75,569 76,570 51,571 40,572 101,573 96,574 74,575 51,576 38,577 90,578 83,579 66,580 46,581 39,582 91,583 41,584 86,585 98,586 74,587 10,588 29,589 58,590 36,591 8,592 78,593 60,594 88,595 47,596 56,597 97,598 52,599 99,600 14,601 55,602 30,603 18,604 70,605 2,606 77,607 8,608 44,609 10,610 15,611 29,612 70,613 37,614 59,615 88,616 76,617 78,618 29,619 31,620 49,621 96,622 7,623 13,624 100,625 17,626 76,627 103,628 85,629 8,630 76,631 68,632 30,633 45,634 81,635 10,636 74,637 70,638 13,639 33,640 31,641 40,642 50,643 103,644 78,645 59,646 14,647 57,648 19,649 75,650 40,651 103,652 17,653 48,654 54,655 15,656 15,657 35,658 4,659 7,660 60,661 19,662 42,663 57,664 11,665 31,666 92,667 102,668 91,669 90,670 62,671 20,672 88,673 13,674 82,675 58,676 77,677 17,678 7,679 58,680 22,681 83,682 43,683 54,684 4,685 61,686 71,687 92,688 93,689 46,690 18,691 66,692 95,693 43,694 35,695 41,696 49,697 89,698 59,699 75,700 29,701 75,702 74,703 31,704 67,705 4,706 98,707 31,708 24,709 96,710 93,711 9,712 90,713 53,714 16,715 104,716 30,717 64,718 40,719 87,720 103,721 15,722 38,723 17,724 74,725 12,726 103,727 87,728 65,729 4,730 77,731 46,732 32,733 84,734 67,735 67,736 100,737 45,738 12,739 102,740 7,741 72,742 55,743 21,744 15,745 13,746 70,747 65,748 93,749 73,750 23,751 19,752 71,753 82,754 42,755 66,756 26,757 7,758 14,759 82,760 32,761 91,762 6,763 53,764 21,765 52,766 56,767 77,768 49,769 74,770 4,771 21,772 69,773 75,774 61,775 63,776 101,777 7,778 33,779 78,780 49,781 28,782 39,783 56,784 30,785 103,786 73,787 92,788 72,789 88,790 18,791 63,792 57,793 71,794 80,795 61,796 99,797 87,798 44,799 41,800 101,801 64,802 17,803 58,804 11,805 77,806 3,807 7,808 71,809 19,810 2,811 93,812 49,813 16,814 22,815 57,816 86,817 83,818 71,819 40,820 31,821 52,822 61,823 46,824 40,825 82,826 1,827 56,828 80,829 71,830 30,831 43,832 87,833 65,834 1,835 77,836 33,837 56,838 90,839 71,840 11,841 41,842 50,843 92,844 20,845 32,846 2,847 37,848 52,849 26,850 86,851 6,852 48,853 60,854 1,855 75,856 66,857 97,858 103,859 25,860 32,861 78,862 11,863 7,864 69,865 87,866 13,867 13,868 49,869 89,870 99,871 62,872 39,873 80,874 81,875 7,876 102,877 13,878 104,879 34,880 98,881 80,882 31,883 4,884 99,885 99,886 64,887 35,888 97,889 41,890 7,891 74,892 61,893 89,894 70,895 91,896 60,897 8,898 84,899 69,900 40,901 51,902 44,903 55,904 47,905 50,906 69,907 46,908 24,909 65,910 79,911 103,912 58,913 84,914 48,915 83,916 21,917 32,918 58,919 81,920 38,921 46,922 4,923 68,924 59,925 78,926 33,927 91,928 93,929 31,930 49,931 55,932 97,933 34,934 33,935 91,936 42,937 22,938 18,939 24,940 22,941 53,942 79,943 28,944 2,945 63,946 51,947 53,948 1,949 4,950 69,951 29,952 10,953 30,954 10,955 102,956 9,957 26,958 39,959 79,960 4,961 25,962 41,963 12,964 53,965 47,966 81,967 52,968 22,969 6,970 44,971 35,972 43,973 37,974 76,975 61,976 47,977 23,978 42,979 63,980 83,981 33,982 10,983 33,984 46,985 91,986 103,987 83,988 12,989 55,990 9,991 34,992 40,993 12,994 87,995 41,996 4,997 88,998 24,999 55,1000 94,1001 12,1002 6,1003 30,1004 74,1005 99,1006 73,1007 24,1008 59,1009 63,1010 93,1011 39,1012 61,1013 15,1014 30,1015 66,1016 74,1017 102,1018 23,1019 68,1020 79,1021 93,1022 32,1023 18,1024 51,1025 53,1026 93,1027 19,1028 90,1029 93,1030 66,1031 67,1032 42,1033 73,1034 35,1035 97,1036 22,1037 98,1038 5,1039 78,1040 98,1041 65,1042 21,1043 54,1044 102,1045 24,1046 50,1047 43,1048 24,1049 47,1050 19,1051 64,1052 76,1053 81,1054 91,1055 78,1056 64,1057 92,1058 67,1059 83,1060 94,1061 25,1062 43,1063 52,1064 18,1065 37,1066 59,1067 31,1068 44,1069 2,1070 2,1071 12,1072 28,1073 50,1074 16,1075 23,1076 40,1077 5,1078 32,1079 63,1080 40,1081 76,1082 72,1083 44,1084 40,1085 9,1086 34,1087 68,1088 63,1089 21,1090 104,1091 44,1092 94,1093 35,1094 95,1095 51,1096 89,1097 76,1098 2,1099 66,1100 49,1101 45,1102 30,1103 38,1104 45,1105 95,1106 32,1107 73,1108 74,1109 3,1110 24,1111 69,1112 44,1113 38,1114 96,1115 9,1116 71,1117 15,1118 101,1119 50,1120 74,1121 5,1122 41,1123 89,1124 46,1125 97,1126 24,1127 84,1128 89,1129 49,1130 31,1131 39,1132 36,1133 16,1134 63,1135 65,1136 33,1137 67,1138 39,1139 20,1140 65,1141 57,1142 44,1143 21,1144 21,1145 100,1146 99,1147 27,1148 65,1149 2,1150 84,1151 47,1152 86,1153 30,1154 40,1155 88,1156 12,1157 69,1158 93,1159 64,1160 90,1161 41,1162 18,1163 39,1164 31,1165 96,1166 38,1167 97,1168 103,1169 55,1170 40,1171 75,1172 60,1173 81,1174 44,1175 9,1176 44,1177 8,1178 30,1179 96,1180 64,1181 102,1182 7,1183 50,1184 82,1185 58,1186 42,1187 70,1188 27,1189 44,1190 51,1191 30,1192 71,1193 57,1194 89,1195 100,1196 10,1197 69,1198 100,1199 52,1200 28,