how many numbers between 1 to 10 billion contains 14

Question

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

Answer 1

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, 10, 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
        }
    }
}