- A+

i tried this code but it takes so long and I can not get the result

` public long getCounter([FromBody]object req) { JObject param = Utility.GetRequestParameter(req); long input = long.Parse(param["input"].ToString()); long counter = 0; for (long i = 14; i <= input; i++) { string s = i.ToString(); if (s.Contains("14")) { counter += 1; } } return counter; } `

please help

We can examine all non-negative numbers < 10^10. Every such number can be represented with the sequence of 10 digits (with leading zeroes allowed).

**How many numbers include 14**

Dynamic programming solution. Let's find the number of sequences of a specific length that ends with the specific digit and contains (or not) subsequence 14:

`F(len, digit, 0)`

is the number of sequences of length `len`

that ends with `digit`

and do not contain 14, `F(len, digit, 1)`

is the number of such sequences that contain 14. Initially `F(0, 0, 0) = 1`

. The result is the sum of all `F(10, digit, 1)`

.

C++ code to play with: https://ideone.com/2aS17v. The answer seems to be 872348501.

**How many times the numbers include 14**

First, let's place 14 at the end of the sequence:

`????????14 `

Every '?' can be replaced with any digit from 0 to 9. Thus, there are 10^8 numbers in the interval that contains 14 at the end. Then consider `???????14?`

, `??????14??`

, ..., `14????????`

numbers. There are 9 possible locations of 14 sequence. The answer is 10^8 * 9 = 90000000.

[Added by Matthew Watson]

Here's the C# version of the C++ implementation; it runs in less than 100ms:

`using System; namespace Demo { public static class Program { public static void Main(string[] args) { const int M = 10; int[,,] f = new int [M + 1, 11, 2]; f[0, 0, 0] = 1; for (int len = 1; len <= M; ++len) { for (int d = 0; d <= 9; ++d) { for (int j = 0; j <= 9; ++j) { f[len,d,0] += f[len - 1,j,0]; f[len,d,1] += f[len - 1,j,1]; } } f[len,4,0] -= f[len - 1,1,0]; f[len,4,1] += f[len - 1,1,0]; } int sum = 0; for (int i = 0; i <= 9; ++i) sum += f[M,i,1]; Console.WriteLine(sum); // 872,348,501 } } } `