algorithm - How many numbers with length N with K digits D consecutively -

algorithm - How many numbers with length N with K digits D consecutively -

given positive numbers n, k, d (1<= n <= 10^5, 1<=k<=n, 1<=d<=9). how many numbers n digits there, have k consecutive digits d? write reply mod (10^9 + 7).

for example: n = 4, k = 3, d = 6, there 18 numbers:

1666, 2666, 3666, 4666, 5666, 6660, 6661, 6662, 6663, 6664, 6665, 6666, 6667, 6668, 6669, 7666, 8666 , 9666.

can calculate reply in o(n*k) (maybe dynamic programming)? i've tried using combination. if

n = 4, k = 3, d = 6. number have find abcd.

+) if (a = b = c = d), take digit d. there 10 ways (6660, 6661, 6662, 6663, 6664, 6665, 6666, 6667, 6668, 6669)

+) if (b = c = d = d), take digit (a > 0). there 9 ways (1666, 2666, 3666, 4666, 5666, 6666, 7666, 8666, 9666) in 2 cases, number 6666 counted twice. n , k large, how can count of them?

if 1 looking mathematical solution (vs. algorithmic one) it's @ in terms of base of operations cases , formulas. might turn out can kind of refactoring , tidy formula for. heck of it...here's take on doesn't deal special treatment of zeros. because throws wrenches in.

let's @ couple of base of operations cases, , phone call our reply f(n,k) (not considering d, isn't relevant business relationship for; taking parameter anyway.):

when n = 0

you'll never find length sequences of digits when there's no digit.

f(0, k) = 0 k. when n = 1

fairly obvious. if you're looking k sequential digits in single digit, options limited. looking more one? no dice.

f(1, k) = 0 k > 1

looking one? okay, there's one.

f(1, 1) = 1

sequences of 0 sequential digits allowed? 10 digits fine.

f(1, 0) = 10 for n > 1 when k = 0

basically, n-digit numbers qualify. number of possibilities meeting bar 10^n. (e.g. when n 3 000, 001, 002, ... 999 d)

f(n, 0) = 10^n n > 1 when k = 1

possibilities meeting status number @ to the lowest degree 1 d in it. how many n-digit numbers there contain @ to the lowest degree 1 digit d? well, it's going 10^n minus numbers have no instances of digit d. 10^n - 9^n

f(n, 1) = 10^n - 9^n n > 1 when n < k

no way k sequential digits if n less k

f(n, k) = 0 when n < k when n = k

only 1 possible way k sequential digits in n digits.

f(n, k) = 1 when n = k when n > k

okay, know n > 1 , k > 1. going workhorse hope utilize subexpressions things we've solved.

let's start considering popping off digit @ head, leaving n-1 digits on tail. if n-1 series accomplish series of k digits itself, adding digit not alter that. gives term 10 * f(n-1, k)

but if our head digit d, special. our cases be:

it might missing key series started k-1 instances of d, creating total range of k.

it might finish range of k-1 instances of d, on case had k series of adjacent d (that accounted in above term)

it might not help @ all.

so let's consider 2 separate categories of tail series: those start k-1 instances of d , not. let's have n=7 shown d:dddxyz , k=4. subtract 1 n , k 6 , 3, , if subtract them how many trailing any-digits (xyz here) allowed vary. our term union of (1) , (2) add together in 10^((n-1)-(k-1)).

now it's time subtraction our double-counts. haven't double counted cases didn't start k-1 instances of d, maintain our attending on (dddxyz). if value in x slot d definitely double counted. can subtract out term 10^(((n - 1) - 1) - (k - 1)); in case giving pairings of yz digits can x d. (100).

the lastly thing rid of cases x not d, in whatever leftover after x position there still k length series of d. 1 time again reuse our function, , subtract term 9 * f(n - k, k, d).

paste , simplify couple of terms get:

f(n, k) = 10 * f(n-1,k,d) + 10^(n-k) - 10^(10,n-k-1) - 9 * f(n-k-1,k,d)

now have nice functional definition suitable haskelling or whatever. i'm still awkward that, , it's easy plenty test in c++. here (assuming availability of long integer power function):

long f(int n, int k, int d) { if (n == 0) homecoming 0; if (k > n) homecoming 0; if (k == n) homecoming 1; if (n == 1) { if (k == 0) homecoming 10; if (k == 1) homecoming 1; homecoming 0; } if (k == 0) homecoming power(10, n); if (k == 1) homecoming power(10, n) - power(9, n); homecoming ( 10 * f(n - 1, k, d) + power(10, n - k) - power(10, n - k - 1) - 9 * f(n - k - 1, k, d) ); }

to double-check against exhaustive generator, here's little c++ test programme builds list of vectors scans using std::search_n. checks slow way against fast way n , k. ran 0 9 each:

#include <iostream> #include <algorithm> #include <vector> using namespace std; // http://stackoverflow.com/a/1505791/211160 long power(int x, int p) { if (p == 0) homecoming 1; if (p == 1) homecoming x; long tmp = power(x, p/2); if (p%2 == 0) homecoming tmp * tmp; else homecoming x * tmp * tmp; } long f(int n, int k, int d) { if (n == 0) homecoming 0; if (k > n) homecoming 0; if (k == n) homecoming 1; if (n == 1) { if (k == 0) homecoming 10; if (k == 1) homecoming 1; homecoming 0; } if (k == 0) homecoming power(10, n); if (k == 1) homecoming power(10, n) - power(9, n); homecoming ( 10 * f(n - 1, k, d) + power(10, n - k) - power(10, n - k - 1) - 9 * f(n - k - 1, k, d) ); } long fslowcore(int n, int k, int d, vector<int> & digits) { if (n == 0) { if (search_n(digits.begin(), digits.end(), k, d) != end(digits)) { homecoming 1; } else homecoming 0; } long total = 0; digits.push_back(0); (int curdigit = 0; curdigit <= 9; curdigit++) { total += fslowcore(n - 1, k, d, digits); digits.back()++; } digits.pop_back(); homecoming total; } long fslow(int n, int k, int d) { vector<int> digits; homecoming fslowcore(n, k, d, digits); } bool testf(int n, int k, int d) { long slow = fslow(n, k, d); long fast = f(n, k, d); cout << "when n = " << n << " , k = " << k << " , d = " << d << ":\n"; cout << "fast way gives " << fast << "\n"; cout << "slow way gives " << slow << "\n"; cout << "\n"; homecoming slow == fast; } int main() { (int n = 0; n < 10; n++) { (int k = 0; k < 10; k++) { if (!testf(n, k, 6)) { exit(1); } } } }

of course, since counts leading zeros different answers got. see the test output here in gist.

modifying business relationship special-case 0 handling left exercise reader (as modular arithmetic). eliminating zeros create messier. either way, may avenue of attack reducing number of math operations farther transformations...perhaps.

algorithm math