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