Problem Statement
The number X appears in the number Y if, when written in base-10, the digits of X form a (not necessarily contiguous) subsequence of the digits of Y. For example, X = 246 appears in Y = 1234567 and X = 222 appears in Y = 222. On the other hand, the numbers 1223 and 31 do not appear in the number 123.
Given a String B containing the base-10 representation of a possibly very large positive integer, count all positive integer multiples of N that appear in B. Return the count modulo 10^9 + 7.
Definition
- Class:
- SubmultiplesOfN
- Method:
- count
- Parameters:
- String, int
- Returns:
- int
- Method signature:
- int count(String B, int N)
- (be sure your method is public)
Constraints
- B will have between 1 and 5,000 characters, inclusive.
- Each character of B will be a digit.
- B will not start with a zero.
- N will be between 1 and 1,000, inclusive.
Examples
"1111111111"
7
Returns: 1
The only positive integer multiple of 7 that appears in the given number is 111,111. Note that we are counting distinct numbers, not their appearances: even though 111,111 can be seen in B in many different ways, we only want to count it once."12345678"
2
Returns: 170
Exactly 170 distinct even numbers appear in 12345678. Some of those numbers are 4, 1346 and 12345678."1357913579135791357913579"
2
Returns: 0
"1122334455"
6
Returns: 20
Four of these 20 numbers are 12, 114, 2244 and 1123344."1020402"
24
Returns: 6
The six multiples of 24 that appear in 1020402 are 24, 120, 240, 1200, 2040, and 10200."123456789012345678901234567890"
1
Returns: 62224120
Don't forget to calculate the answer modulo 10^9 + 7.