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