TheRealSamuel/LeetCodeProblem
0564
1{2 "id": 3080,3 "name": "split_array_into_maximum_number_of_subarrays",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/split-array-into-maximum-number-of-subarrays/",6 "date": "2023-09-16 00:00:00",7 "task_description": "You are given an array `nums` consisting of **non-negative** integers. We define the score of subarray `nums[l..r]` such that `l <= r` as `nums[l] AND nums[l + 1] AND ... AND nums[r]` where **AND** is the bitwise `AND` operation. Consider splitting the array into one or more subarrays such that the following conditions are satisfied: **E****ach** element of the array belongs to **exactly** one subarray. The sum of scores of the subarrays is the **minimum** possible. Return _the **maximum** number of subarrays in a split that satisfies the conditions above._ A **subarray** is a contiguous part of an array. **Example 1:** ``` **Input:** nums = [1,0,2,0,1,2] **Output:** 3 **Explanation:** We can split the array into the following subarrays: - [1,0]. The score of this subarray is 1 AND 0 = 0. - [2,0]. The score of this subarray is 2 AND 0 = 0. - [1,2]. The score of this subarray is 1 AND 2 = 0. The sum of scores is 0 + 0 + 0 = 0, which is the minimum possible score that we can obtain. It can be shown that we cannot split the array into more than 3 subarrays with a total score of 0. So we return 3. ``` **Example 2:** ``` **Input:** nums = [5,7,1,3] **Output:** 1 **Explanation:** We can split the array into one subarray: [5,7,1,3] with a score of 1, which is the minimum possible score that we can obtain. It can be shown that we cannot split the array into more than 1 subarray with a total score of 1. So we return 1. ``` **Constraints:** `1 <= nums.length <= 105` `0 <= nums[i] <= 106`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [1,0,2,0,1,2]",12 "output": "3 "13 },14 {15 "label": "Example 2",16 "input": "nums = [5,7,1,3]",17 "output": "1 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 891476,24 951533,25 357789,26 946246,27 214115,28 337892,29 570309,30 843813,31 495285,32 441039,33 159172,34 676602,35 63226,36 928016,37 202244,38 80214,39 741867,40 137035,41 851604,42 283449,43 135252,44 654498,45 756489,46 501358,47 159319,48 722783,49 995586,50 466343,51 761520,52 368237,53 363552,54 417718,55 31072,56 40306,57 38661,58 739835,59 686411,60 281403,61 404433,62 580987,63 31823,64 295731,65 811138,66 611030,67 825621,68 49037,69 99641,70 190850,71 81872,72 80101,73 313314,74 583552,75 614257,76 475164,77 551971,78 56301,79 646656,80 736634,81 199894,82 737781,83 641689,84 573432,85 160717,86 789638,87 723228,88 297870,89 531789,90 471010,91 90347,92 778695,93 74332,94 959394,95 207010,96 979921,97 97621,98 94805,99 420273,100 865415,101 360715,102 832507,103 428117,104 989341,105 585284,106 833343,107 396007,108 734933,109 179620,110 519350,111 242458,112 844179,113 819048,114 788453,115 164214,116 38204,117 806186,118 488153,119 97878,120 645073,121 442241,122 599474,123 431367,124 67168,125 686656,126 592950,127 41440,128 548911,129 192732,130 493908,131 925400,132 498449,133 588621,134 153658,135 197722,136 20770,137 859479,138 13757,139 670879,140 707817,141 820975,142 665560,143 864569,144 794641,145 799507,146 696667,147 151291,148 115101,149 503400,150 834041,151 152196,152 397747,153 455223,154 880611,155 123623,156 775268,157 464963,158 976410,159 61302,160 687668,161 626756,162 665252,163 435959,164 783764,165 325981,166 851711,167 447292,168 722291,169 254680,170 82425,171 480072,172 552667,173 696752,174 208226,175 356696,176 262785,177 339957,178 849384,179 725085,180 418446,181 780548,182 8979,183 175970,184 112694,185 776070,186 167143,187 730059,188 277418,189 262891,190 654031,191 504435,192 166134,193 495860,194 32308,195 270615,196 919876,197 506062,198 72819,199 441770,200 236254,201 384796,202 315270,203 932897,204 153046,205 703345,206 796627,207 38844,208 114356,209 418366,210 588627,211 404438,212 180753,213 411643,214 827447,215 545697,216 274962,217 83644,218 926977,219 765385,220 160151,221 880786,222 463249,223 981539,224 873085,225 374663,226 719458,227 865676,228 48836,229 748773,230 986435,231 816735,232 640970,233 919083,234 57958,235 979383,236 773416,237 488085,238 9516,239 276310,240 441837,241 265,242 776548,243 170561,244 406019,245 828983,246 315861,247 31464,248 941617,249 28301,250 269199,251 544860,252 187528,253 876493,254 724366,255 648760,256 738270,257 16514,258 27334,259 845628,260 983669,261 233434,262 703688,263 857047,264 752004,265 533043,266 217382,267 221252,268 110042,269 776239,270 900019,271 479856,272 300532,273 173254,274 28198,275 327696,276 366137,277 438334,278 78263,279 665339,280 225192,281 380268,282 761662,283 683312,284 908470,285 478319,286 46504,287 412153,288 426047,289 901753,290 614481,291 974684,292 137966,293 643989,294 229499,295 60444,296 349773,297 681116,298 442916,299 466019,300 164537,301 346019,302 353440,303 388947,304 711967,305 910130,306 260519,307 450167,308 985867,309 555593,310 951597,311 984219,312 794762,313 490828,314 648418,315 863295,316 205964,317 421378,318 84488,319 995479,320 240735,321 779751,322 343752,323 144602,324 842388,325 870065,326 603022,327 182680,328 275865,329 770678,330 376998,331 910800,332 899162,333 32375,334 337943,335 405550,336 753864,337 71441,338 229190,339 825879,340 676232,341 462666,342 193726,343 676277,344 955085,345 247453,346 166757,347 975413,348 461714,349 156290,350 240802,351 633914,352 71033,353 27397,354 699278,355 243309,356 777025,357 246637,358 549711,359 251801,360 766864,361 280455,362 39987,363 632516,364 412165,365 717713,366 566018,367 670260,368 594821,369 584832,370 363217,371 603333,372 141225,373 974111,374 373178,375 348626,376 699745,377 254682,378 553931,379 4161,380 972813,381 379726,382 580304,383 918720,384 65267,385 500428,386 644626,387 329816,388 194604,389 271772,390 109182,391 336346,392 910453,393 429069,394 417761,395 325951,396 793582,397 807673,398 525674,399 747974,400 465588,401 924211,402 951506,403 963507,404 756078,405 930365,406 427728,407 731961,408 496562,409 603834,410 72519,411 156022,412 963119,413 368967,414 359829,415 744432,416 349781,417 497236,418 57509,419 623918,420 929030,421 699191,422 936463,423 452762,424 21727,425 842434,426 934662,427 537195,428 632563,429 707452,430 58477,431 289691,432 84919,433 764105,434 799827,435 660493,436 105086,437 954980,438 639063,439 492180,440 734579,441 84928,442 284980,443 903137,444 733685,445 686076,446 231836,447 68035,448 855731,449 653704,450 565229,451 680573,452 678289,453 732903,454 812353,455 851598,456 254269,457 760865,458 84269,459 714369,460 209961,461 795572,462 514156,463 60104,464 392131,465 911175,466 628537,467 909410,468 255782,469 598364,470 291092,471 213092,472 513993,473 543351,474 392841,475 879009,476 809704,477 625134,478 256299,479 793326,480 409667,481 853555,482 135168,483 149416,484 271646,485 581486,486 808579,487 61875,488 330705,489 236803,490 400633,491 852634,492 68932,493 277441,494 288499,495 563599,496 556003,497 150745,498 310088,499 617228,500 159687,501 193745,502 860199,503 916575,504 232306,505 681331,506 831237,507 233664,508 331980,509 375467,510 533974,511 640814,512 282885,513 952298,514 80419,515 821023,516 577194,517 971031,518 806589,519 339243,520 995260,521 680772,522 632922,523 554516,524 371082,525 655408,526 813151,527 610003,528 106641,529 744573,530 187118,531 245839,532 377944,533 601217,534 559709,535 53256,536 683915,537 47070,538 238439,539 607598,540 179924,541 43971,542 445687,543 389227,544 140,545 271691,546 214414,547 39171,548 94580,549 346912,550 964413,551 723753,552 438890,553 906200,554 851990,555 570140,556 745671,557 36631,558 877012,559 875191,560 401339,561 664494,562 755175,563 556566,564 189368,565 903088,566 791620,567 332471,568 969701,569 820475,570 494954,571 326356,572 959400,573 186590,574 8988,575 254392,576 580328,577 953791,578 652812,579 449150,580 506111,581 962600,582 923858,583 608813,584 622410,585 286831,586 438654,587 972679,588 819548,589 599064,590 607970,591 792328,592 480763,593 967242,594 574611,595 477570,596 46016,597 591591,598 170958,599 820683,600 717144,601 634734,602 910224,603 777808,604 980632,605 582827,606 151125,607 382765,608 881533,609 393253,610 660099,611 629962,612 899536,613 21644,614 361221,615 508875,616 78945,617 776938,618 195386,619 38148,620 456790,621 252712,622 302420,623 672682,624 305710,625 769610,626 956949,627 748710,628 669739,629 184857,630 252422,631 600761,632 215420,633 807532,634 433026,635 197123,636 996094,637 161851,638 363255,639 685239,640 706963,641 899080,642 138827,643 559826,644 642514,645 325095,646 820205,647 870460,648 70693,649 451370,650 209000,651 284616,652 685332,653 533153,654 262623,655 686353,656 124589,657 181325,658 596806,659 790130,660 238647,661 189599,662 763730,663 736709,664 839422,665 279656,666 664771,667 781279,668 153840,669 325423,670 127565,671 435294,672 788275,673 865848,674 629553,675 47661,676 476650,677 226548,678 733215,679 22614,680 276383,681 610223,682 760119,683 82725,684 952424,685 271415,686 251338,687 398330,688 314541,689 710686,690 679419,691 929133,692 735,693 808832,694 727188,695 856114,696 286331,697 129498,698 644251,699 912614,700 681462,701 41367,702 218708,703 256421,704 840389,705 592816,706 438084,707 678113,708 468296,709 552695,710 508504,711 662685,712 969046,713 951245,714 583010,715 818407,716 859611,717 407749,718 611548,719 668915,720 458984,721 680551,722 938834,723 209950,724 853627,725 827621,726 551251,727 25360,728 382396,729 602677,730 305228,731 711560,732 791038,733 99299,734 64185,735 499874,736 483470,737 505779,738 269754,739 760252,740 934084,741 72102,742 895613,743 310022,744 196751,745 636297,746 399292,747 292027,748 258599,749 845445,750 586229,751 117109,752 797873,753 848048,754 803939,755 384670,756 168994,757 255084,758 928527,759 232475,760 605112,761 903266,762 443144,763 97387,764 385875,765 493695,766 755545,767 611434,768 503839,769 78712,770 661173,771 902174,772 374435,773 23760,774 222622,775 400804,776 832003,777 72115,778 818422,779 558761,780 234136,781 750071,782 219717,783 671160,784 471514,785 53555,786 92423,787 366364,788 956033,789 432485,790 448672,791 797031,792 482593,793 853434,794 374700,795 955271,796 457551,797 798928,798 553859,799 295383,800 960705,801 850141,802 386838,803 405174,804 397574,805 374443,806 421731,807 15001,808 376544,809 372498,810 76819,811 314138,812 794111,813 745677,814 41914,815 982592,816 844610,817 884243,818 143372,819 334565,820 960649,821 24775,822 794067,823 125652,824 452494,825 196556,826 160131,827 48969,828 215266,829 690154,830 683760,831 732805,832 649422,833 248834,834 345892,835 165743,836 116339,837 630382,838 898322,839 421328,840 32734,841 356990,842 273318,843 358026,844 852806,845 481191,846 16720,847 686046,848 330383,849 34139,850 326168,851 983342,852 325666,853 473354,854 94398,855 320491,856 126038,857 850229,858 265558,859 219399,860 541972,861 224983,862 339508,863 723017,864 648552,865 245900,866 77952,867 487820,868 453531,869 610034,870 859352,871 733928,872 775198,873 709381,874 525139,875 745386,876 894142,877 988070,878 517163,879 686189,880 587404,881 291251,882 50124,883 941056,884 937255,885 873322,886 953443,887 887707,888 537619,889 870607,890 680495,891 299752,892 359341,893 808817,894 123852,895 236274,896 230958,897 125744,898 30353,899 264416,900 387154,901 981357,902 409286,903 98841,904 985923,905 325267,906 97647,907 997955,908 501209,909 959693,910 262958,911 968142,912 646513,913 581993,914 355374,915 879120,916 202081,917 372805,918 747727,919 3993,920 465152,921 858603,922 414945,923 154506,924 705213,925 970075,926 365293,927 284087,928 75813,929 535894,930 776956,931 611605,932 347688,933 65532,934 12290,935 117285,936 358528,937 32530,938 132508,939 958667,940 249627,941 437036,942 273887,943 492260,944 138056,945 544888,946 498995,947 560908,948 829877,949 427726,950 781487,951 413873,952 858702,953 876467,954 676285,955 736224,956 678396,957 207506,958 383761,959 617162,960 312885,961 741073,962 614413,963 459302,964 469484,965 20958,966 85863,967 472425,968 471607,969 958284,970 796495,971 158320,972 627000,973 12589,974 390093,975 792047,976 494884,977 55948,978 629311,979 941828,980 354779,981 392555,982 142394,983 555561,984 839434,985 102401,986 34143,987 844325,988 107891,989 92025,990 979038,991 792382,992 693335,993 55433,994 89872,995 598794,996 18518,997 510250,998 332728,999 421669,1000 762602,1001 667114,1002 208741,1003 741350,1004 880458,1005 755951,1006 993821,1007 155211,1008 456023,1009 935086,1010 603140,1011 15236,1012 289857,1013 582391,1014 280036,1015 745632,1016 380884,1017 100413,1018 117387,1019 591987,1020 38423,1021 689026,1022 712618,1023 857407,1024 352264,1025 732860,1026 902206,1027 444963,1028 191066,1029 670278,1030 274775,1031 490881,1032 197478,1033 64180,1034 751264,1035 722377,1036 375249,1037 877589,1038 143266,1039 221703,1040 721951,1041 747029,1042 645031,1043 569220,1044 294933,1045 467119,1046 560943,1047 300859,1048 246320,1049 366825,1050 615072,1051 835031,1052 213456,1053 646329,1054 418188,1055 127708,1056 698327,1057 247836,1058 826544,1059 502201,1060 177468,1061 427055,1062 800704,1063 118212,1064 289731,1065 246777,1066 336611,1067 132022,1068 827665,1069 451794,1070 764505,1071 420893,1072 723783,1073 254231,1074 472312,1075 412009,1076 875257,1077 15882,1078 316357,1079 308406,1080 484067,1081 628115,1082 351583,1083 64391,1084 84882,1085 737141,1086 717201,1087 479449,1088 779402,1089 595926,1090 680656,1091 184958,1092 258460,1093 925298,1094 779128,1095 39414,1096 591891,1097 430283,1098 178640,1099 783947,1100 293342,1101 124091,1102 69184,1103 195379,1104 325054,1105 866841,1106 138223,1107 991525,1108 398055,1109 459556,1110 785291,1111 181563,1112 528037,1113 830331,1114 548751,1115 169471,1116 615779,1117 473810,1118 248946,1119 10322,1120 605776,1121 335217,1122 112987,1123 830847,1124 170257,1125 413895,1126 743691,1127 924827,1128 66998,1129 835480,1130 201332,1131 866869,1132 571296,1133 478415,1134 185343,1135 162229,1136 403524,1137 73085,1138 626252,1139 628213,1140 296370,1141 416943,1142 747722,1143 178367,1144 354232,1145 793608,1146 6501,1147 285866,1148 365189,1149 790735,1150 139155,1151 95758,1152 929576,1153 785916,1154 301883,1155 514819,1156 140303,1157 706071,1158 34723,1159 90761,1160 202286,1161 833554,1162 22545,1163 446216,1164 705300,1165 437687,1166 264017,1167 203343,1168 950218,1169 800767,1170 811087,1171 701401,1172 583962,1173 561867,1174 91550,1175 523719,1176 133307,1177 553593,1178 966259,1179 748696,1180 684633,1181 306719,1182 218184,1183 286410,1184 759792,1185 982936,1186 390270,1187 769255,1188 460422,1189 796228,1190 165604,1191 943395,1192 674449,1193 544996,1194 453843,1195 512728,1196 514546,1197 616538,1198 744848,1199 936990,1200 16864,