Problem Statement
A number is an up-number if we can erase all but S of its digits in such a way that the remaining S digits form a strictly increasing sequence.
For example, 12141176 is an up-number if S = 4 (e.g., we can produce the sequence 1 2 4 6) but it's no longer an up-number if S = 5.
Similarly, a number is a down-number if we can do the same for a strictly decreasing sequence of S digits.
And finally, a number that is both an up-number and a down-number is called an updown-number.
Count all positive integers with exactly D decimal digits that are updown-numbers. Return that count modulo 10^9 + 7.
Definition
- Class:
- UpdownNumbers
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int D, int S)
- (be sure your method is public)
Constraints
- D will be between 1 and 100, inclusive.
- S will be between 1 and 10, inclusive.
Examples
1
1
Returns: 9
For S = 1 each number is an updown-number. There are nine positive integers with exactly 1 digit: the numbers 1 through 9.
3
2
Returns: 525
For S = 2 the numbers that are not updown-numbers are precisely the numbers with digits in sorted order (counting both non-decreasing and non-increasing order as "sorted"). We can enumerate and check all three-digit integers to verify this answer.
20
2
Returns: 986881317
We can also be smarter and get the answers for S = 2 by doing some combinatorics to count the numbers with digits in sorted order, and then subtracting that count from the count of all D-digit numbers.Make sure to compute and return the answer using the right modulus.
8
5
Returns: 0
It's reasonably easy to show that there cannot be any 8-digit updown-numbers for S = 5: if we color any 5-digit increasing subsequence red and any 5-digit decreasing subsequence blue, there cannot be more than one number that's both red and blue.
8
3
Returns: 73017588
100
10
Returns: 112069402
46
2
Returns: 600980963
56
9
Returns: 270539434
59
10
Returns: 188112362
44
5
Returns: 398043888
66
7
Returns: 894663977
51
10
Returns: 892016724
6
7
Returns: 0
85
1
Returns: 817539548
14
1
Returns: 999370007
34
8
Returns: 122157315
93
9
Returns: 47264719
2
6
Returns: 0
73
7
Returns: 165973876
30
4
Returns: 840344178
67
9
Returns: 98190721
46
8
Returns: 980631068
31
1
Returns: 996913007
72
6
Returns: 188967576
92
6
Returns: 445139270
77
6
Returns: 599928846
72
10
Returns: 649525346
98
4
Returns: 40469719
31
1
Returns: 996913007
17
6
Returns: 534501157
13
6
Returns: 280395426
75
7
Returns: 436182865
66
9
Returns: 166699371
33
2
Returns: 149859962
84
4
Returns: 661569348
90
6
Returns: 556207879
28
8
Returns: 34128441
96
2
Returns: 99049325
99
7
Returns: 70090461
78
6
Returns: 833871505
87
5
Returns: 454204856
99
4
Returns: 734605221
72
5
Returns: 782053477
46
9
Returns: 220250189
73
1
Returns: 51883209
62
5
Returns: 597182255
73
7
Returns: 165973876
34
9
Returns: 559053165
29
10
Returns: 380279768
15
4
Returns: 846933141
49
8
Returns: 992145668
33
10
Returns: 238615581
72
3
Returns: 716037181
57
1
Returns: 105884100
22
9
Returns: 31888507
81
2
Returns: 985905716
10
5
Returns: 71849078
66
10
Returns: 382879398
70
8
Returns: 915254059
56
6
Returns: 289147623
98
1
Returns: 232040596
78
5
Returns: 266358249
83
10
Returns: 699246818
67
8
Returns: 708082469
91
6
Returns: 617927915
3
10
Returns: 0
32
4
Returns: 86068090
45
7
Returns: 7027764
89
3
Returns: 525652245
23
8
Returns: 170065302
26
3
Returns: 652845171
13
3
Returns: 700669147
94
10
Returns: 751999642
45
9
Returns: 9149733
51
2
Returns: 873086182
35
8
Returns: 248392215