java - 如何计算包含一个数字但不包含另一个数字的数字？

Question

我最近遇到一个面试问题，虽然它有一个显而易见的解决方案，但我很难找到一个更有效的解决方案。

实际问题涉及计算从 a 到 b 的数字(最多 2^64)，这满足了数字 6 或 8，但不能同时使用。他们称之为“幸运数字”。例如:

126 - lucky
88 - lucky
856 - not lucky

显而易见的想法是通过将 a 和 b 之间的每个数字作为字符串进行测试来暴力破解它，以检查相关字符。然而，这如预期的那样慢得令人望而却步。

我尝试过一个更好的解决方案，涉及首先计算所有“幸运数字”，这些数字的位数介于 a 和 b 的位数之间(通过计算可能的组合):

long n = 0;

for (int occurrences = 1; occurrences <= maxDigits; occurrences++) {

    n += (long) Math.pow(8, digits - occurrences) * choose(digits, occurrences);
}

return 2 * n;

然后使用蛮力法计算我数过的额外幸运数字的数量。例如，如果 a = 3 和 b = 21，我可以计算 1 和 2 的数量数字幸运数字，然后减去 [1, 3) 和 (21, 99] 中的数字。

然而，尽管这是一个巨大的改进，但在大多数情况下，蛮力元素仍然大大降低了它的速度。

我觉得一定有我遗漏的东西，因为其余的面试问题都比较简单。有没有人有更好的解决方案？

---

<支持>虽然我已经用 Java 标记了这个问题，但同样感谢任何其他语言或伪代码的帮助。

Answer 1

我会说你走在正确的轨道上。直觉是分别处理 a 和 b 更容易。制作函数 count_lucky_numbers_below(n) 允许

return count_lucky_numbers_below(b) - count_lucky_numbers_below(a);

组合方法绝对是一种可行的方法(请记住，总和实际上等于 9**n - 8**n，并且无需计算二项式系数)。

最后一个技巧是向下递归一个数字。

假设 n 是一个 N 位数字，最高有效位是 5。每组 N 位数字开始较小的数字对总数贡献 S = 9**(N-1) - 8**(N-1)；您立即拥有 5*S 个幸运数字。要处理余数，您需要计算 N-1 位尾部的幸运数字。

当然，如果最高位在5以上就得注意了，6或8需要特例，不过好像也不算太复杂。