1到100亿之间有多少数字包含14

Question

我尝试了这段代码,但需要很长时间,我无法得到结果

    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;
    }

请帮忙

Answer 1

我们可以检查所有非负数<10 ^ 10.每个这样的数字可以用10位数的序列表示(允许前导零).

有多少数字包括14

动态编程解决方案 让我们找到以特定数字结尾并包含(或不包含)子序列14的特定长度的序列数:

F(len, digit, 0)是以14 len结尾digit但不包含14 的长度序列的数量,F(len, digit, 1)是包含14 的此类序列的数量.最初F(0, 0, 0) = 1.结果是所有的总和F(10, digit, 1).

要使用的C++代码:https://ideone.com/2aS17v.答案似乎是872348501.

这些数字包括14次

首先,让我们在序列的末尾放置14:

????????14

每个'？' 可以替换为0到9之间的任何数字.因此,在间隔中有10 ^ 8个数字,最后包含14个.然后考虑???????14?,??????14??......,14????????数字.14个序列有9个可能的位置.答案是10 ^ 8*9 = 90000000.

[Matthew Watson补充]

这是C++实现的C#版本; 它运行时间不到100毫秒:

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

Answer 2

如果你想有一个蛮力解决方案也可能是这样的(请,通知,我们应该避免耗时的字符串操作一样ToString,Contains):

  int count = 0;

  // Let's use all CPU's cores: Parallel.For 
  Parallel.For(0L, 10000000000L, (v) => {  
    for (long x = v; x > 10; x /= 10) {
      // Get rid of ToString and Contains here
      if (x % 100 == 14) {
        Interlocked.Increment(ref count); // We want an atomic (thread safe) operation

        break;
      }
    }
  });

  Console.Write(count);

它872348501在6分钟内返回(Core i7,4核,3.2GHz)

Answer 3

您计算给定长度以 1、4 或其他不包含 14 结尾的数字的计数。然后您可以将长度扩展 1。

那么包含14 的数字的计数就是所有数字减去不包含 14 的数字的计数。

private static long Count(int len) {
   long e1=0, e4=0, eo=1;
   long N=1;
   for (int n=0; n<len; n++) {
       long ne1 = e4+e1+eo, ne4 = e4+eo, neo = 8*(e1+e4+eo);
       e1 = ne1; e4 = ne4; eo = neo;
       N *= 10;
   }
   return N - e1 - e4 - eo;
}

您可以稍微减少此代码，注意eo = 8*e1除了第一次迭代之外，然后避免局部变量。

private static long Count(int len) {
   long e1=1, e4=1, N=10;
   for (int n=1; n<len; n++) {
       e4 += 8*e1;
       e1 += e4;
       N *= 10;
   }
   return N - 9*e1 - e4;
}

对于这两者，Count(10)返回 872348501。