-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path1498--number-of-subsequences-that-satisfy-the-given-sum-condition.js
115 lines (107 loc) · 20.1 KB
/
1498--number-of-subsequences-that-satisfy-the-given-sum-condition.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// 1498. Number of Subsequences That Satisfy the Given Sum Condition
// https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/
// Medium
//
// You are given an array of integers nums and an integer target.
// Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 109 + 7.
// Example 1:
// Input: nums = [3,5,6,7], target = 9
// Output: 4
// Explanation: There are 4 subsequences that satisfy the condition.
// [3] -> Min value + max value <= target (3 + 3 <= 9)
// [3,5] -> (3 + 5 <= 9)
// [3,5,6] -> (3 + 6 <= 9)
// [3,6] -> (3 + 6 <= 9)
// Example 2:
// Input: nums = [3,3,6,8], target = 10
// Output: 6
// Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
// [3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
// Example 3:
// Input: nums = [2,3,3,4,6,7], target = 12
// Output: 61
// Explanation: There are 63 non-empty subsequences, two of them do not satisfy the condition ([6,7], [7]).
// Number of valid subsequences (63 - 2 = 61).
// Constraints:
// 1 <= nums.length <= 105
// 1 <= nums[i] <= 106
// 1 <= target <= 106
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var numSubseq = function (nums, target) {
nums.sort((a, b) => a - b);
const mod = 1e9 + 7;
let pow = [];
pow.push(1);
for (let i = 1; i < nums.length; i++) {
pow.push((pow[pow.length - 1] * 2) % mod);
}
let leftIndex = 0;
let rightIndex = nums.length - 1;
let answer = 0;
while (leftIndex <= rightIndex && nums[leftIndex] * 2 <= target) {
if (nums[leftIndex] + nums[rightIndex] > target) {
rightIndex--;
} else {
answer = (answer + pow[rightIndex - leftIndex++]) % mod;
}
}
return answer;
};
// -- OR --
//
//
//
// /**
// * @param {number[]} nums
// * @param {number} target
// * @return {number}
// */
// const findRight = (nums, target) => {
// let left = 0;
// let right = nums.length;
// while (left < right) {
// let mid = (left + right) >> 1;
// if (nums[mid] <= target) {
// left = mid + 1;
// } else {
// right = mid;
// }
// }
// return left;
// };
//
// /**
// * @param {number[]} nums
// * @param {number} target
// * @return {number}
// */
// const numSubseq = (nums, target) => {
// let numsCount = nums.length;
// let mod = Math.pow(10, 9) + 7;
// nums.sort((a, b) => a - b);
//
// let pow = [];
// pow.push(1);
// for (let i = 1; i < numsCount; i++) {
// pow.push((pow[i - 1] << 1) % mod);
// }
//
// let answer = 0;
//
// for (let left = 0; left < numsCount; left++) {
// let right = findRight(nums, target - nums[left]) - 1;
// if (right >= left) {
// answer += pow[right - left];
// } else {
// break;
// }
// }
// return answer % mod;
// };
let testNums = [120, 410, 959, 493, 70, 622, 299, 306, 591, 346, 150, 115, 291, 376, 917, 960, 910, 958, 121, 801, 257, 114, 109, 591, 749, 134, 665, 76, 656, 230, 504, 369, 263, 490, 166, 143, 981, 64, 315, 788, 955, 888, 830, 535, 683, 502, 178, 445, 811, 292, 639, 248, 680, 320, 460, 603, 881, 536, 768, 681, 512, 795, 112, 761, 543, 990, 900, 449, 56, 940, 559, 820, 675, 782, 882, 241, 102, 241, 957, 990, 160, 219, 705, 886, 411, 405, 467, 454, 75, 632, 681, 618, 518, 398, 889, 469, 895, 466, 835, 250, 922, 662, 115, 218, 184, 201, 332, 349, 436, 906, 78, 512, 805, 196, 381, 521, 994, 771, 712, 268, 942, 532, 877, 438, 377, 850, 953, 543, 435, 728, 933, 695, 858, 400, 726, 123, 912, 972, 119, 341, 418, 433, 218, 785, 533, 539, 791, 851, 672, 898, 961, 284, 506, 608, 673, 249, 822, 732, 381, 523, 411, 806, 311, 284, 614, 838, 370, 799, 167, 366, 945, 299, 764, 365, 176, 604, 430, 399, 655, 342, 792, 64, 935, 633, 853, 171, 527, 889, 842, 69, 141, 539, 383, 698, 766, 162, 120, 521, 431, 143, 70, 241, 948, 281, 977, 455, 727, 127, 969, 271, 699, 272, 288, 338, 374, 778, 582, 645, 945, 675, 131, 167, 522, 524, 686, 713, 747, 988, 255, 956, 389, 946, 135, 1000, 608, 91, 522, 465, 316, 244, 812, 495, 601, 165, 211, 770, 661, 493, 735, 700, 395, 177, 945, 887, 284, 484, 533, 357, 769, 576, 699, 559, 854, 151, 701, 512, 657, 668, 436, 530, 727, 269, 424, 289, 186, 547, 755, 588, 447, 865, 616, 712, 667, 654, 676, 908, 649, 941, 191, 211, 322, 870, 527, 109, 482, 401, 403, 238, 828, 554, 890, 608, 817, 797, 67, 517, 118, 385, 230, 467, 425, 887, 984, 948, 909, 948, 113, 698, 160, 431, 856, 530, 823, 298, 253, 152, 748, 592, 639, 788, 600, 305, 93, 373, 996, 755, 473, 899, 721, 89, 702, 663, 361, 747, 549, 604, 999, 422, 348, 332, 139, 61, 670, 271, 373, 248, 992, 837, 137, 391, 439, 84, 692, 498, 513, 199, 516, 737, 959, 691, 891, 420, 906, 648, 773, 290, 957, 578, 642, 814, 253, 321, 200, 666, 711, 466, 273, 421, 194, 503, 110, 814, 294, 353, 543, 105, 787, 668, 122, 444, 248, 983, 171, 985, 512, 871, 560, 910, 778, 192, 141, 739, 616, 617, 65, 787, 305, 829, 485, 945, 109, 559, 57, 723, 658, 468, 218, 836, 246, 443, 142, 372, 678, 264, 432, 955, 438, 945, 418, 630, 69, 378, 851, 100, 467, 541, 853, 396, 566, 594, 433, 197, 994, 915, 676, 891, 485, 900, 785, 182, 896, 830, 283, 981, 632, 642, 779, 686, 407, 346, 382, 291, 876, 543, 427, 222, 301, 601, 596, 586, 989, 220, 648, 492, 276, 351, 858, 60, 601, 267, 497, 660, 480, 115, 254, 654, 173, 356, 760, 991, 975, 357, 817, 149, 563, 705, 258, 505, 278, 749, 981, 275, 202, 864, 462, 694, 625, 783, 272, 226, 964, 716, 684, 226, 849, 452, 241, 801, 66, 589, 983, 639, 117, 523, 501, 292, 719, 968, 621, 153, 956, 138, 804, 734, 393, 323, 779, 417, 656, 455, 85, 698, 149, 978, 298, 902, 78, 451, 743, 722, 760, 174, 563, 555, 100, 494, 653, 774, 580, 154, 52, 345, 825, 568, 469, 209, 913, 562, 124, 961, 503, 701, 83, 368, 105, 417, 381, 997, 417, 626, 181, 695, 192, 280, 570, 392, 148, 410, 804, 241, 687, 819, 697, 343, 909, 264, 357, 279, 155, 994, 748, 203, 379, 141, 990, 467, 515, 451, 912, 987, 896, 743, 632, 224, 180, 960, 1000, 479, 172, 165, 326, 294, 877, 217, 319, 115, 880, 423, 741, 836, 421, 533, 840, 135, 406, 586, 330, 434, 473, 854, 651, 781, 181, 602, 344, 850, 170, 702, 394, 135, 210, 608, 536, 482, 95, 146, 529, 805, 276, 250, 164, 488, 709, 57, 847, 950, 282, 979, 105, 888, 774, 131, 559, 390, 587, 685, 551, 628, 116, 726, 947, 543, 992, 227, 440, 153, 163, 897, 689, 360, 479, 646, 764, 173, 76, 291, 893, 695, 810, 660, 647, 803, 593, 555, 254, 256, 958, 583, 408, 762, 208, 987, 330, 895, 725, 729, 454, 471, 946, 497, 393, 710, 913, 423, 184, 689, 189, 891, 987, 760, 254, 895, 294, 136, 784, 534, 571, 574, 107, 871, 287, 292, 980, 775, 564, 675, 221, 944, 508, 182, 196, 654, 263, 638, 652, 664, 878, 889, 133, 759, 469, 975, 782, 432, 882, 911, 877, 910, 717, 691, 797, 411, 759, 399, 219, 931, 753, 841, 132, 151, 465, 323, 817, 213, 728, 862, 431, 55, 413, 93, 220, 427, 390, 439, 357, 881, 358, 858, 109, 967, 378, 432, 767, 877, 906, 682, 416, 106, 650, 821, 950, 569, 464, 779, 556, 830, 464, 504, 524, 114, 751, 405, 547, 309, 322, 844, 608, 830, 241, 561, 346, 856, 945, 698, 888, 778, 371, 222, 139, 927, 960, 849, 637, 413, 905, 372, 976, 197, 938, 636, 710, 644, 120, 87, 924, 849, 462, 584, 662, 992, 467, 424, 504, 125, 824, 971, 226, 763, 75, 400, 862, 581, 123, 748, 141, 724, 564, 863, 993, 365, 277, 356, 848, 372, 259, 623, 703, 190, 470, 700, 290, 891, 626, 706, 854, 490, 396, 408, 627, 834, 178, 303, 711, 774, 221, 707, 1000, 849, 382, 929, 465, 837, 741, 441, 347, 894, 221, 995, 558, 356, 472, 587, 216, 908, 551, 102, 68, 632, 651, 999, 835, 260, 153, 329, 320, 255, 854, 886, 842, 522, 202, 263, 811, 226, 899, 192, 590, 678, 442, 406, 601, 789, 803, 482, 529, 762, 778, 584, 648, 760, 556, 68, 148, 611, 713, 923, 816, 345, 58, 128, 899, 883, 362, 325, 641, 990, 826, 835, 135, 744, 727, 734, 759, 802, 752, 862, 738, 854, 708, 857, 259, 478, 107, 311, 480, 654, 767, 360, 184, 236, 331, 220, 537, 779, 983, 434, 135, 630, 291, 410, 142, 493, 167, 504, 172, 84, 305, 815, 785, 609, 566, 541, 177, 461, 403, 963, 925, 541, 298, 787, 212, 407, 132, 450, 941, 739, 525, 900, 905, 727, 428, 555, 939, 996, 644, 350, 117, 130, 73, 248, 821, 848, 689, 471, 452, 938, 268, 663, 301, 472, 410, 195, 296, 264, 708, 663, 762, 356, 733, 667, 730, 455, 914, 121, 266, 348, 454, 768, 558, 954, 563, 544, 152, 802, 709, 550, 796, 84, 556, 942, 453, 799, 755, 933, 332, 310, 813, 57, 307, 329, 966, 963, 761, 788, 242, 645, 399, 352, 795, 119, 894, 577, 210, 202, 115, 954, 395, 589, 785, 819, 741, 829, 408, 360, 819, 487, 963, 319, 673, 679, 621, 173, 549, 203, 708, 630, 139, 891, 254, 994, 599, 961, 496, 391, 485, 746, 723, 399, 736, 632, 826, 684, 937, 560, 701, 667, 611, 292, 729, 152, 741, 505, 188, 894, 362, 514, 616, 898, 470, 257, 373, 884, 274, 272, 780, 539, 932, 872, 534, 815, 846, 748, 337, 476, 367, 420, 323, 118, 657, 819, 464, 447, 611, 697, 318, 834, 617, 549, 363, 366, 156, 94, 518, 74, 734, 497, 639, 421, 996, 822, 472, 540, 479, 608, 941, 100, 97, 794, 219, 464, 850, 420, 529, 835, 561, 704, 353, 146, 786, 551, 325, 560, 591, 793, 96, 260, 640, 292, 200, 340, 338, 959, 275, 587, 708, 836, 591, 178, 822, 50, 469, 792, 857, 583, 428, 846, 468, 211, 407, 586, 70, 750, 478, 422, 171, 468, 715, 254, 131, 221, 651, 476, 517, 641, 555, 662, 390, 188, 541, 157, 405, 332, 932, 350, 813, 756, 804, 496, 532, 760, 793, 570, 951, 625, 616, 576, 645, 555, 825, 765, 315, 369, 325, 364, 877, 433, 879, 168, 530, 364, 417, 932, 86, 340, 448, 759, 238, 806, 694, 869, 87, 138, 997, 305, 527, 250, 523, 271, 708, 51, 892, 750, 822, 137, 986, 310, 565, 572, 67, 332, 967, 420, 895, 82, 687, 577, 446, 405, 114, 285, 335, 778, 841, 747, 903, 414, 347, 986, 318, 740, 837, 150, 272, 771, 418, 890, 880, 203, 991, 244, 589, 624, 241, 362, 424, 79, 473, 269, 217, 700, 981, 241, 453, 917, 684, 112, 265, 253, 408, 303, 751, 98, 713, 183, 78, 840, 771, 181, 330, 157, 267, 696, 289, 53, 466, 888, 546, 823, 975, 944, 104, 508, 933, 400, 275, 818, 403, 366, 791, 246, 852, 685, 476, 278, 711, 1000, 366, 381, 787, 380, 467, 384, 59, 254, 724, 648, 450, 332, 248, 728, 214, 827, 864, 907, 512, 264, 101, 396, 552, 336, 373, 975, 231, 401, 561, 640, 585, 789, 433, 800, 897, 300, 328, 798, 565, 472, 110, 75, 451, 414, 169, 813, 91, 488, 177, 325, 527, 100, 250, 899, 84, 845, 599, 543, 956, 855, 839, 965, 496, 904, 605, 405, 977, 67, 231, 417, 578, 65, 270, 155, 759, 585, 942, 360, 524, 240, 200, 626, 320, 855, 288, 671, 953, 350, 541, 707, 59, 817, 641, 383, 800, 575, 53, 183, 878, 331, 898, 351, 796, 861, 360, 255, 52, 678, 736, 519, 775, 715, 834, 977, 627, 143, 681, 221, 382, 973, 305, 557, 562, 243, 292, 81, 802, 867, 664, 273, 792, 991, 238, 614, 827, 259, 462, 590, 99, 785, 240, 163, 967, 931, 380, 607, 315, 531, 919, 371, 669, 305, 935, 176, 744, 659, 805, 793, 455, 575, 534, 477, 829, 77, 186, 688, 143, 947, 210, 68, 794, 500, 83, 689, 116, 232, 82, 436, 138, 212, 563, 791, 56, 654, 444, 838, 579, 338, 883, 686, 442, 246, 932, 171, 808, 729, 370, 335, 947, 598, 492, 655, 828, 937, 435, 321, 972, 856, 643, 338, 570, 872, 417, 580, 92, 876, 958, 205, 849, 706, 725, 406, 220, 779, 493, 760, 730, 889, 940, 250, 591, 791, 309, 483, 504, 787, 196, 274, 914, 907, 394, 293, 149, 366, 625, 645, 475, 557, 105, 162, 118, 869, 435, 308, 434, 883, 229, 534, 475, 461, 507, 106, 200, 120, 997, 706, 818, 266, 724, 610, 67, 143, 979, 992, 98, 61, 890, 438, 625, 473, 151, 841, 683, 656, 745, 611, 878, 110, 764, 265, 671, 673, 785, 832, 457, 542, 434, 629, 275, 156, 549, 472, 473, 797, 642, 906, 726, 231, 912, 172, 499, 785, 132, 585, 829, 721, 722, 326, 92, 887, 742, 819, 76, 818, 390, 688, 251, 572, 631, 281, 926, 520, 767, 67, 266, 846, 382, 373, 140, 280, 860, 750, 168, 986, 798, 493, 762, 169, 641, 468, 347, 970, 936, 829, 549, 445, 91, 333, 274, 99, 945, 549, 161, 890, 650, 128, 743, 125, 602, 400, 903, 860, 982, 349, 298, 607, 639, 356, 891, 929, 905, 154, 336, 941, 235, 330, 817, 631, 898, 532, 613, 180, 440, 213, 515, 84, 336, 858, 237, 879, 430, 329, 546, 718, 351, 434, 791, 409, 238, 150, 374, 850, 405, 309, 255, 172, 145, 339, 725, 190, 196, 346, 851, 818, 645, 280, 549, 379, 386, 468, 680, 599, 874, 69, 278, 655, 603, 261, 769, 260, 460, 493, 784, 933, 516, 339, 979, 850, 207, 250, 453, 746, 408, 298, 639, 634, 425, 636, 475, 631, 927, 337, 829, 936, 357, 821, 744, 257, 599, 182, 877, 909, 357, 107, 426, 183, 129, 84, 115, 63, 579, 652, 372, 413, 80, 82, 810, 459, 390, 351, 315, 186, 989, 412, 647, 130, 395, 160, 467, 934, 476, 309, 525, 415, 599, 58, 270, 477, 404, 497, 953, 680, 163, 571, 211, 185, 395, 688, 687, 57, 255, 444, 591, 745, 983, 152, 167, 98, 584, 132, 523, 295, 105, 354, 901, 896, 162, 428, 657, 817, 423, 954, 88, 90, 581, 453, 803, 90, 820, 607, 843, 877, 539, 809, 310, 949, 749, 63, 834, 930, 408, 147, 444, 267, 681, 926, 415, 360, 903, 169, 419, 848, 662, 618, 484, 787, 546, 896, 978, 728, 344, 527, 146, 673, 534, 195, 585, 86, 300, 659, 873, 495, 377, 574, 734, 315, 643, 366, 441, 636, 499, 781, 825, 952, 198, 116, 116, 312, 596, 474, 476, 645, 807, 490, 947, 89, 278, 571, 99, 783, 633, 475, 906, 745, 812, 725, 195, 145, 61, 351, 206, 310, 157, 883, 119, 942, 852, 498, 521, 439, 616, 326, 970, 954, 860, 816, 895, 619, 708, 793, 695, 424, 438, 843, 159, 885, 74, 413, 165, 982, 481, 727, 370, 799, 661, 506, 220, 982, 793, 62, 721, 908, 133, 467, 503, 431, 180, 202, 299, 838, 690, 430, 735, 827, 285, 370, 206, 307, 623, 656, 709, 971, 701, 753, 684, 269, 995, 291, 955, 299, 354, 193, 603, 719, 858, 837, 476, 652, 921, 281, 740, 582, 706, 622, 675, 935, 548, 609, 817, 644, 509, 283, 395, 158, 759, 76, 590, 666, 251, 762, 84, 490, 69, 623, 373, 75, 499, 911, 714, 577, 259, 985, 604, 488, 772, 692, 698, 929, 693, 341, 531, 630, 239, 490, 862, 431, 51, 998, 116, 822, 247, 222, 737, 489, 182, 270, 431, 629, 490, 447, 659, 932, 909, 584, 806, 192, 510, 970, 147, 557, 865, 554, 609, 674, 378, 183, 574, 656, 88, 483, 77, 909, 63, 445, 527, 96, 753, 883, 766, 384, 464, 232, 144, 903, 206, 463, 914, 221, 189, 480, 185, 238, 691, 57, 460, 603, 186, 295, 241, 351, 707, 656, 926, 517, 521, 134, 276, 703, 853, 530, 895, 652, 420, 675, 299, 260, 721, 817, 782, 601, 544, 236, 703, 640, 850, 889, 627, 646, 487, 692, 396, 271, 52, 923, 75, 222, 637, 840, 899, 335, 819, 398, 833, 558, 729, 550, 982, 940, 795, 771, 495, 630, 941, 605, 289, 958, 199, 842, 492, 921, 911, 894, 423, 839, 432, 929, 733, 113, 362, 538, 222, 881, 658, 390, 218, 314, 603, 306, 642, 718, 568, 92, 673, 902, 941, 367, 77, 916, 392, 538, 187, 360, 762, 725, 263, 354, 165, 114, 668, 682, 428, 195, 829, 403, 791, 238, 924, 605, 584, 656, 118, 595, 466, 174, 442, 984, 795, 710, 966, 913, 802, 563, 768, 743, 953, 635, 557, 660, 358, 669, 436, 824, 114, 104, 493, 242, 460, 114, 384, 64, 553, 720, 153, 573, 137, 265, 460, 109, 554, 612, 361, 718, 849, 842, 823, 458, 297, 912, 706, 606, 260, 909, 506, 713, 750, 806, 304, 846, 635, 952, 230, 253, 919, 436, 442, 681, 989, 152, 421, 527, 587, 509, 344, 267, 978, 327, 513, 973, 992, 275, 463, 800, 944, 644, 568, 737, 302, 116, 410, 446, 847, 999, 543, 106, 87, 166, 181, 424, 116, 231, 222, 246, 72, 192, 651, 556, 554, 591, 161, 935, 727, 736, 688, 276, 154, 676, 434, 718, 691, 177, 350, 882, 90, 400, 137, 772, 683, 341, 444, 823, 811, 648, 512, 547, 890, 582, 634, 944, 196, 738, 627, 754, 374, 760, 111, 679, 956, 938, 323, 828, 976, 418, 610, 875, 348, 890, 784, 801, 644, 340, 133, 331, 431, 297, 71, 434, 466, 64, 283, 813, 393, 312, 522, 656, 464, 515, 722, 700, 873, 643, 855, 352, 336, 980, 884, 360, 436, 890, 601, 915, 500, 468, 600, 456, 344, 708, 659, 569, 478, 392, 70, 917, 249, 838, 176, 776, 537, 705, 705, 170, 978, 222, 452, 353, 57, 984, 205, 981, 908, 539, 363, 995, 907, 375, 199, 944, 913, 205, 473, 278, 723, 201, 718, 689, 617, 863, 311, 630, 311, 262, 602, 914, 596, 119, 943, 975, 873, 445, 328, 298, 564, 618, 502, 178, 717, 833, 123, 907, 127, 921, 245, 745, 518, 172, 980, 529, 53, 348, 432, 413, 613, 365, 544, 961, 543, 658, 81, 508, 742, 882, 747, 475, 999, 470, 292, 128, 698, 754, 640, 514, 568, 494, 142, 867, 174, 333, 84, 745, 282, 677, 345, 147, 653, 232, 948, 855, 471, 510, 84, 940, 906, 95, 749, 568, 223, 817, 80, 95, 625, 356, 332, 218, 724, 836, 93, 520, 311, 701, 317, 298, 926, 318, 555, 446, 134, 821, 318, 712, 485, 426, 296, 718, 905, 793, 780, 978, 377, 237, 254, 521, 832, 211, 949, 273, 659, 718, 162, 752, 702, 593, 257, 894, 291, 154, 416, 836, 253, 510, 704, 190, 543, 200, 466, 920, 560, 979, 102, 302, 228, 550, 631, 803, 668, 668, 741, 814, 322, 637, 552, 186, 883, 918, 251, 627, 163, 218, 431, 791, 285, 929, 50, 372, 627, 300, 434, 748, 805, 408, 210, 844, 96, 732, 841, 86, 307, 99, 776, 823, 726, 389, 601, 707, 383, 384, 76, 160, 798, 835, 943, 691, 132, 834, 310, 142, 838, 428, 294, 734, 374, 459, 640, 170, 302, 189, 537, 592, 752, 253, 69, 119, 854, 592, 551, 735, 702, 185, 316, 495, 441, 498, 798, 591, 821, 923, 961, 933, 670, 247, 93, 434, 326, 434, 208, 965, 802, 635, 924, 58, 578, 843, 636, 261, 184, 569, 970, 732, 269, 535, 552, 820, 772, 579, 793, 577, 301, 454, 650, 904, 686, 900, 528, 466, 933, 647, 124, 479, 420, 82, 482, 326, 432, 862, 853, 424, 281, 772, 95, 851, 898, 552, 847, 893, 931, 453, 665, 992, 580, 273, 680, 684, 488, 758, 261, 606, 251, 87, 471, 274, 760, 479, 640, 151, 159, 832, 144, 254, 777, 510, 405, 665, 881, 661, 790, 674, 349, 320, 73, 833, 879, 336, 205, 253, 690, 145, 240, 789, 249, 670, 901, 553, 312, 468, 935, 142, 302, 703, 754, 796, 263, 874, 954, 160, 57, 610, 72, 561, 505, 545, 535, 904, 936, 295, 350, 716, 949, 601, 984, 276, 383, 271, 824, 107, 785, 88, 83, 512, 107, 68, 487, 921, 221, 883, 941, 642, 327, 121, 60, 779, 717, 389, 222, 637, 805, 204, 844, 252, 478, 712, 531, 1000, 616, 173, 829, 834, 498, 946, 913, 943, 647, 565, 655, 815, 564, 939, 664, 694, 52, 97, 167, 963, 778, 943, 287, 937, 137, 957, 118, 834, 363, 914, 503, 644, 825, 935, 638, 413, 296, 896, 290, 62, 199, 191, 682, 774, 633, 271, 898, 918, 622, 739, 738, 116, 604, 832, 453, 428, 794, 755, 506, 518, 221, 988, 265, 926, 802, 153, 434, 184, 366, 699, 537, 835, 473, 647, 361, 463, 834, 982, 738, 67, 882, 806, 713, 257, 434, 597, 376, 704, 923, 227, 979, 173, 496, 122, 86, 627, 632, 435, 469, 133, 530, 973, 663, 853, 249, 314, 492, 824, 852, 968, 954, 586, 787, 482, 490, 748, 586, 214, 254, 942, 512, 983, 438, 192, 500, 438, 112, 428, 807, 315, 174, 792, 634, 700, 419, 957, 358, 178, 752, 295, 510, 175, 223, 515, 511, 996, 787, 338, 816, 471, 747, 943, 589, 254, 398, 500, 579, 507, 207, 318, 981, 873, 123, 851, 904, 486, 935, 136, 740, 307, 279, 959, 667, 541, 800, 523, 557, 379, 313, 824, 375, 593, 845, 904, 106, 616, 154, 150, 121, 753, 446, 203, 438, 716, 450, 897, 605, 696, 704, 257, 823, 623, 651, 554, 53, 92, 826, 102, 496, 907, 451, 225, 184, 933, 787, 203, 966, 584, 331, 396, 301, 982, 643, 997, 843, 726, 519, 582, 651, 202, 153, 302, 431, 68, 643, 161, 538, 239, 959, 709, 167, 367, 634, 685, 333, 952, 411, 849, 863, 322, 720, 454, 740, 531, 104, 249, 76, 300, 950, 592, 309, 466, 452, 506, 153, 669, 388, 406, 979, 495, 717, 320, 66, 167, 529, 268, 236, 276, 207, 894, 476, 420, 469, 911, 395, 430, 390, 867, 227, 731, 205, 368, 776, 275, 485, 741, 152, 953, 211, 1000, 266, 758, 235, 693, 809, 952, 884, 495, 561, 53, 610, 670, 383, 713, 928, 924, 481, 401, 753, 824, 720, 982, 280, 700, 972, 337, 707, 186, 609, 670, 758, 216, 317, 193, 586, 583, 179, 155, 960, 885, 458, 523, 510, 270, 551, 591, 634, 312, 811, 594, 640, 64, 204, 867, 280, 169, 664, 247, 630, 689, 771, 941, 186, 165, 875, 73, 935, 401, 218, 638, 570, 873, 148, 210, 547, 780, 304, 865, 513, 979, 585, 712, 750, 681, 830, 936, 823, 712, 585, 963, 73, 628, 579, 976, 245, 122, 140, 280, 166, 615, 732, 757, 1000, 81, 769, 613, 741, 607, 622, 127, 274, 124, 298, 60, 992, 917, 390, 814, 162, 536, 984, 237, 983, 435, 703, 849, 104, 822, 214, 583, 630, 379, 398, 228, 974, 262, 514, 562, 871, 236, 208, 647, 478, 748, 911, 830, 69, 508, 156, 437, 395, 246, 693, 785, 781, 384, 52, 486, 537, 262, 408, 764, 138, 866, 458, 889, 817, 512, 860, 628, 221, 166, 464, 559, 171, 770, 719, 217, 283, 178, 658, 691, 494, 808, 235, 321, 876, 670, 968, 564, 781, 341, 762, 934, 744, 195, 418, 138];
let testTarget = 579;
console.log(numSubseq(testNums, testTarget));