algorithm - 一种在给定限制 'l' (0 <= l <= 10^16) 中查找数字数量的算法，其中至少出现一次单个数字 'n' ？

Question

首先，这不是一道作业题。我正在经历一些组合问题以通过算法解决，我真的只需要着手解决这个问题。

我最初的想法是声明一个大小为 17 的数组，对其进行初始化并运行一个循环以使用简单搜索查找出现的数字，例如“5”。但解决方案看起来乏味且丑陋。

1. 对如何表示大数 (10^16) 有什么想法吗？
2. 是否有解决此类问题的简单组合公式/算法？

谢谢。

Answer 1

假设您的意思是 0 <= l < 10^16(不是 <= 10^16)，此范围内的所有整数都有 10 位数字(允许前导 0)。此范围内共有 10^16 个值。我会把问题写成:

有数字 n 的数字 = 10^16 - 没有数字 n 的数字。

那么有多少种方法可以让我们不在 1 的位置选择 n 呢？ 9种方式。我们有多少种方法可以不在 10 或 1 的位置放置“n”？ 9*9。按照这个逻辑，有 9^16 种方法可以不将 n 放入 16 个可能的位置中的任何一个。

所以你的答案是 10^16 - 9^16。

如果您实际上是指 0 <= l <= 16，则该范围只有一个数字，即 10^16。这个数字的前导数字是 1，所以如果 n = 1，你就有 10^16 - 9^16 + 1 个值，其中有一个 1。如果 n != 1 则之前的答案成立。