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