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