如何计算包含一位数字但不包含另一位数字的数字

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

实际问题涉及从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 中标记了这个问题，但同样希望得到任何其他语言或伪代码的帮助。}

我会说你走在正确的轨道上。直觉是，分别处理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，但它似乎并不太复杂。

最后，@user58697的回答将我推向了寻找解决方案的正确方向。使用我的(尽管非常原始)基准测试，它可以在不到 2 纳秒的时间内处理1到2^63 - 1，因此它绝对足够快。然而，它仍然比我想要的更冗长，特别是考虑到我最初希望在半小时内写完它，所以我觉得仍然有一个更简单的解决方案可以提供相当的性能。

long countLuckyNumbersBetween(long a, long b) {
return countLuckyNumbersBelow(b) - countLuckyNumbersBelow(a - 1);
}
long countLuckyNumbersBelow(long n) {
return countNumbers(n, 6, 8) + countNumbers(n, 8, 6);
}
/**
* Counts the natural numbers in [0, {to}] that have {including} as a digit, but not {excluding}.
* {excluding} should be in (0, 9] or -1 to exclude no digit.
*/
long countNumbers(long to, int including, int excluding) {
if (including == -1) return 0;
if (to < 10) {
if (to >= including) {
return 1;
} else {
return 0;
}
}
int nSignificand = significand(to);
int nDigits = countDigits(to);
long nTail = to % (long) Math.pow(10, nDigits - 1);
// The count of numbers in [0, 10^(nDigits-1)) that include and exclude the relevant digits
long bodyCount;
if (excluding == -1) {
bodyCount = (long) (Math.pow(10, nDigits - 1) - Math.pow(9, nDigits - 1));
} else {
bodyCount = (long) (Math.pow(9, nDigits - 1) - Math.pow(8, nDigits - 1));
}
long count = 0;
for (int i = 0; i < nSignificand; i++) {
if (i == including) {
if (excluding == -1) {
count += Math.pow(10, nDigits - 1);
} else {
count += Math.pow(9, nDigits - 1);
}
} else if (i != excluding) {
count += bodyCount;
}
}
if (nSignificand == including) {
count += 1 + nTail - countNumbers(nTail, excluding, -1);
} else if (nSignificand != excluding) {
count += countNumbers(nTail, including, excluding);
}
return count;
}
int significand(long n) {
while (n > 9) n /= 10;
return (int) n;
}
int countDigits(long n) {
if (n <= 1) {
return 1;
} else {
return (int) (Math.log10(n) + 1);
}
}

这是另一种方法：

2⁶⁴= 18446744073709551616

我们可以将数字表示为分量的总和(每个数字位置一个分量)：

18446744073709551616              associated range of numbers
————————————————————      ———————————————————————————————————————————
0xxxxxxxxxxxxxxxxxxx  =>  [00000000000000000000;09999999999999999999]
17xxxxxxxxxxxxxxxxxx  =>  [10000000000000000000;17999999999999999999]
183xxxxxxxxxxxxxxxxx  =>  [18000000000000000000;18399999999999999999]
1843xxxxxxxxxxxxxxxx  =>  [18400000000000000000;18439999999999999999]
18445xxxxxxxxxxxxxxx  =>  [18440000000000000000;18445999999999999999]
...
1844674407370955160x  =>  [18446744073709551600;18446744073709551609]
18446744073709551616  =>  [18446744073709551610;18446744073709551616]

如果我们可以计算每个组件的幸运数字数量，那么每个组件的金额总和将是 2⁶⁴的总金额。

注意，每个组件都包含一个前缀，后跟xs.
想象一下，我们知道一个 n 位xx..x中有多少幸运数字(即数字[0..0 - 9..9])，我们称之为N(n)。

现在让我们看一个组件18445x..x。其中18445是前缀和n位xx..x.
在此组件中，我们查看从18440xx..x到18445xx..x的所有数字 .
对于每个项目1844dxx..x我们查看前缀1844d：

如果前缀不包含6或8，则它与没有前缀的x..x相同 =>N(n)特殊数字
如果前缀包含6且不包含8，则x..x不能包含8=>9ⁿ特殊数字
如果前缀包含8且不包含6，则x..x不能包含6=>9ⁿ特殊数字
如果前缀包含6和8=>0特殊数字

现在让我们计算N(n)— n 位xx..x中的幸运数字数量(即以[0..0 - 9..9]为单位).
我们可以迭代地做到这一点：

n=1：只有 2 个可能的数字：8和6=>N(1)=2。
n=2：有2组：
- 8存在：8x和x8其中x是除6以外的任何数字
- 6存在：6x和x6其中x是除8之外的任何数字
=>N(2)=4*9=34.
n=3：让我们修复第一个数字：
- 0xx—5xx，7xx，9xx=>8 * N(2)
- 6xx：除8=>9²之外的任何 2 位数字xx
- 8xx：除6=>9²之外，xx是任何 2 位数字 =>N(3) = 8*N(2) + 2*9².
n=k+1=>N(k+1) = 7*N(k) + 2*9ᵏ

这是一个实现(不是 100% 测试)：

public final class Numbers {
public long countLuckyNumbersBelow(BigInteger num) {
if (num.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("num < 0: " + num);
}
var numberText = num.toString();
var result = 0L;
for (var digitPosition = 0; digitPosition < numberText.length(); digitPosition++) {
result += countLuckyNumbersForComponent(numberText, digitPosition);
}
return result;
}
private long countLuckyNumbersForComponent(String numberText, int digitPosition) {
var prefixEndIdx = numberText.length() - 1 - digitPosition;
var prefixHas6s = containsChar(numberText, '6', prefixEndIdx);
var prefixHas8s = containsChar(numberText, '8', prefixEndIdx);
if (prefixHas6s && prefixHas8s) {
return 0;
}
var result = 0L;
for (var c = numberText.charAt(prefixEndIdx) - 1; c >= '0'; c--) {
var compNo6s = (!prefixHas6s) && (c != '6');
var compNo8s = (!prefixHas8s) && (c != '8');
if (compNo6s && compNo8s) {
result += countLuckyNumbers(digitPosition);
} else if (compNo6s || compNo8s) {
result += power9(digitPosition);
}
}
return result;
}
private static boolean containsChar(String text, char c, int endIdx) {
var idx = text.indexOf(c);
return (idx > 0) && (idx < endIdx);
}
private long[] countLuckyNumbersCache = {0L, 0L};
/**
* Computes how many lucky numbers are in an n-digit `xx..x`
*/
private long countLuckyNumbers(int numDigits) {
if (countLuckyNumbersCache[0] == numDigits) {
return countLuckyNumbersCache[1];
}
long N;
if (numDigits <= 1) {
N = (numDigits == 1) ? 2 : 0;
} else {
var prevN = countLuckyNumbers(numDigits - 1);
N = (8 * prevN) + (2 * power9(numDigits-1));
}
countLuckyNumbersCache[0] = numDigits;
countLuckyNumbersCache[1] = N;
return N;
}
private long[] power9Cache = {0L, 1L};
/**
* Computes 9<sup>power</sup>
*/
private long power9(int power) {
if (power9Cache[0] == power) {
return power9Cache[1];
}
long res = 1;
var p = power;
if (power > power9Cache[0]) {
p -= power9Cache[0];
res = power9Cache[1];
}
for (; p > 0; p--) {
res *= 9;
}
power9Cache[0] = power;
power9Cache[1] = res;
return res;
}
}

顺便说一句，我花了半天时间，我不知道怎么可能在 30 分钟内完成它.
我想你的面试官希望你向他们展示你的思维过程。

这是我尝试的结果。

首先，让我稍微解释一下我使用了什么逻辑。

我使用公式S = 9^N— 8^N(在 user58697 的答案中提到)来计算有多少 N 位数字是幸运的.
如何获得这个公式：

对于 N 位数字，总共有10^N个数字：N位数字，每个数字可以取 10 个值之一：[0-9].
如果我们只计算数字而不计算6，那么每个数字只能取 9 个值中的一个[0-5,7-9]— 总共是9^N个数字
现在我们还只想要8.
的数字，我们可以很容易地计算出有多少数字没有6和8：这些数字中的数字只能取 8 个值中的一个[0-5,7,9]— 总共是8^N个数字.
因此，有S = 9^N— 8^N个数字有8个，没有6。

对于有6和没有8的数字，公式是相同的.
此外，没有6的数字不会与没有8的数字相交 - 因此我们可以将它们相加。

最后，由于我们知道如何计算区间的幸运数[0;10^N]，我们需要将区间[0; our arbitrary number]拆分为合适的子区间.
例如，我们可以这样9845637分割数字：

N 位间隔style="text-align： left;">0000000 - 8999999style="text-align： left;">9000000 - 9799999style="text-align： left;">9800000 - 9839999style="文本对齐：左;">9840000 - 9844999style="text-align： left;">9845000 - 9845599style="text-align： left;">9845600 - 9845629style="文本对齐：左;">9845630 - 9845637

sub-interval	前缀	Digit

	`0 - 8`	`000000 - 999999`

`9`	`0 - 7`	`00000 - 99999`

`98`	`0 - 3`	`0000 - 9999`

`984`	`0 - 4`	`000 - 999`

`9845`	`0 - 5`	`00 - 99`

`98456`	`0 - 2`	`0 - 9`

相关内容

最新更新

热门标签：