c++ - 提高该算法的速度

Question

我试图让这段代码运行得更快，但我在这样做时遇到了麻烦。我可以通过大部分测试用例，但随着数字变大，我无法通过它们。

Input: 92871036442 3363728910382456 output: 1160053175781729
Input: 1 1000000000000000000        output: 264160473575034274 

这些测试用例不会通过。我可以做些什么来加速我的算法并防止它超时？

#include<iostream>

using namespace std;

bool isLuckyNumber(unsigned long long n)
{
    bool found6 = false, found8 = false;
    
    while (n > 0)
    {
        int digit = n % 10;
        if (digit == 6)
        {
            found6 = true;
        }
        else if (digit == 8)
        {
            found8 = true;
        }
        
        //removing last digit
        n = n / 10;
    }
    
    if (found6 && found8)
    {
        return false;
    }
    //otherwise if any one of them is true, it is a lucky number
    else if (found6 || found8)
    {
        return true;
    }
    
    //otherwise not a lucky number
    return false;
}

int main()
{
    //creating needed variables, using unsigned long long as data type as it
    //can store huge values (between 0 and 18446744073709551615)
    unsigned long long L, R, count = 0;
    
    //reading L and R
    cin >> L >> R;
    
    //looping as long as L<=R
    while (L <= R)
    {
        //if L is lucky number, incrementing count
        
        if (isLuckyNumber(L))
        {
            count++;
        }
        
        //incrementing L
        L++;
    }
    
    //displaying count at the end
    cout << count << endl;
    return 0;
}

Answer 1

考虑 0 - 10ⁿ-1 范围内的数字，它们是 10 个数字重复的组合。

不带指定数字的组合数量为 9ⁿ，如果要排除两位数字则为 8ⁿ。

幸运数字被定义为包含 6 或 8 但不能同时包含两者的一组组合。使用基本的集合论我们可以提取一些公式。

N 是基数 |N| 的总范围= 10ⁿ

N-6、N-8 是不包含 6 或 8 的数字集合，|N-6| =|N-8| = 9ⁿ

N-68，既不包含 6 也不包含 8 的数字，|N-68| = 8ⁿ。

由此我们可以计算所有基数:

|N+6| =|N| - |N-6|

|N+8| =|N| - |N-8|

|N+6| + |N+8| - |N+68| + |N-68| = |N|

|幸运| =|N+6| + |N+8| - |N+68| *2 = 2 * ( 9ⁿ - 8ⁿ )

现在，我们需要知道不是 10 的幂范围内的幸运数字，然后我们必须将输入分成几个 block ，每个 block 的形式为 J * 10^K - (J+1) * 10^K - 1。

此类 block 的数量与输入大小成线性关系，即不超过 10 * [[number + 1] 的位数]，因此算法的总成本也与输入大小成线性关系，即 log (n) 其中 n 是输入中的最大数字。

在计算每个 block 时，我们必须考虑 J，前缀:

• 如果 J 同时包含 6 和 8，我们可以跳过该 block ，因为该数字是 不太幸运
• 如果 J 包含 6 或 8 但不同时包含两者，则该 block 的公式为 |N-8|或|N-6| = 9^K
• 在其余情况下，公式为 9^K - 8^K。

所以，总共:

• 为您的输入数字加 1，因为算法排除了范围的上限
• 将您的号码分成几 block
• 计算幸运数字和每个输入数字，然后将它们相减得出结果

要进行快速检查，请考虑范围为 1 到 1000000000000000000(18 位数字)的情况，因为 1 和 1000000000000000000 并不幸运，您可以直接应用公式 2 * ( 9¹⁸ - 8 ¹⁸ )。

代码:

#include <iostream>
using namespace std;

long countLucky(long number) {
    //Algorithm excludes upper bound, so increase it by to include
    number++;

    long ncopy=number;
    //Count digits
    int size=0;
    while (ncopy>0) {
        ncopy/=10;
        size++;
    }

    ncopy=number;

    //Extract digits into array
    int digits[size];
    for (int d=0;ncopy>0;d++) {
        digits[d]=ncopy%10;
        ncopy/=10;
    }

    //Calculate powers of 10, 9, 8 starting with size-1
    long pow10=1;
    long pow9=1;
    long pow8=1;
    for (int i=0;i<size-1;i++) {
        pow10*=10;
        pow9*=9;
        pow8*=8;
    }

    bool prefix6=false;
    bool prefix8=false;

    long count=0;

    for (int d=size-1;d>=0;d--) {
        //Both digits present in prefix, so no more lucky numbers can be found
        if (prefix6 && prefix8) {
            break;
        }
        for (int block=0;block<digits[d];block++) {
            if ((prefix6 || (block==6)) && (prefix8 || (block==8))) {
                continue;
            }
            if ((prefix6 || (block==6)) || (prefix8 || (block==8))) {
                count+=pow9;
            } else {
                count+=2*(pow9-pow8);
            }
        }

        //Calculate new powers
        pow10/=10;
        pow9/=9;
        pow8/=8;

        //Update prefix status
        prefix6 = prefix6 || (digits[d]==6);
        prefix8 = prefix8 || (digits[d]==8);
    }

    cout << endl;

    return count;
}

int main() {
    long c=countLucky(3363728910382456)-countLucky(92871036442);
    cout << "Result    " << c << endl;
    cout << "Solution  " << 1160053175781729 << endl;
}