c++ 高效地找到给定范围内每个数字为6或8的数字

我必须取两个数字，并找到这两个数字之间的所有数字（包括6或8），但不能都是。因此，输入6 8将返回2，而输入60 69将返回9（因为68不计算在内）。
这是一件非常简单的事情，但我必须在不到一秒的时间内完成，即使是在千万亿的数字上。这是不可能迭代完成的事实，这让我想知道是否有一些基本的技巧可以跳过检查我错过的99%的数字。我能优化的最多的是能够进行10^ [two less than the number of digits in the difference between the two numbers]的跳跃，让我们将指数定义为d。我让我程序在数字有数字6和8，或者没有这两个数字时进行这些跳转，并以至少d个零结束。如果数字没有数字6和8，在1和10之间的具有6或8的数字的数量的值被添加到特殊数字的数量（被添加的该第一值已经被保存在存储器中的数组中）。
在任何情况下，我认为展示我尝试的解决方案的最佳方式是展示我的代码。不过，如果您对改进我的问题有任何建议，请随时提出。

#include <iostream>

int main() {
    int_fast64_t low; //starting number
    int_fast64_t high; //ending number
    std::cin >> low >> high; std::cin.ignore();
    /*Starts out holding the difference between high and low,
    then will hold two less than the number of digits in that difference*/
    int_fast64_t lowHighDifference = high - low;
    //10 to various powers used to not have to iterate over every number between low & high
    static int_fast64_t pow10[] = {0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    //The number of numbers with 6 xor 8 between 1 and 10^index
    static int_fast64_t numspecial[] = {0, 2, 34, 434, 4930, 52562, 538594, 5371634, 52539010, 506405522};
    //Find how large the jumps one can make are based on the difference between high and low
    for (int_fast8_t iterator = 9; iterator > 0; iterator--) {
        if (lowHighDifference > pow10[iterator]) {
            /*This needs to have two fewer digits than the difference between low & high,
                otherwise it risks not being used*/
            lowHighDifference = iterator - 1;
            iterator = 0;
        }
    }
    /*Incremented by one every time a number with 6 xor 8 is ecountered,
    and by numspecial[lowHighDifference] every time a number without 6 or 8,
    and at least as many zeros at the end as pow10[lowHighDifference] is encountered*/
    int_fast64_t specialNumbers = 0;
    for (int_fast64_t iterator = low; iterator <= high; iterator++) {
        char stringNum[21]; //long ints can't have more than 20 digits
        /*Copy iterator into a string to check each digit individually,
            while recording the length that string ends up being. */
        int_fast8_t stringNumLength = sprintf(stringNum, "%ld", iterator),
            /*Starts at 0, will turn to 6 or 8 with the first of those found,
                then will be set to -1 if the other number is found */
            sixOrEight = 0;
        for (int_fast8_t stringNumIterator = 0; stringNumIterator < stringNumLength; stringNumIterator++) {
            if (stringNum[stringNumIterator] == '8') {
                if (sixOrEight == 6) {
                    sixOrEight = -1;
                    stringNumIterator = stringNumLength;
                }
                else
                    sixOrEight = 8;
            }
            else if (stringNum[stringNumIterator] == '6') {
                if (sixOrEight == 8) {
                    sixOrEight = -1;
                    stringNumIterator = stringNumLength;
                }
                else
                    sixOrEight = 6;
            }
        }
        /*The basic case in which a six or an eight was found. I don't know how I can optimize this,
        but it's the main part slowing this program down. */
        if (sixOrEight > 0) {
            specialNumbers++;
        }
        else if (lowHighDifference > 0) {
            //If neither six or eight were found
            if (sixOrEight == 0) {
                if (iterator % pow10[lowHighDifference] == 0 && pow10[lowHighDifference] < (high - iterator)) {
                    specialNumbers += numspecial[lowHighDifference];
                    iterator += pow10[lowHighDifference] - 1;
                }
            } //If sixOrEight is < 0 and iterator has at least as many zeros at the end as pow10[lowHighDifference]
            else if (iterator % pow10[lowHighDifference] == 0) {
                //Add 10^lowHighDifference to iterator without adding to specialNumbers
                iterator += pow10[lowHighDifference] - 1;
            }
        }
    }
    std::cout << specialNumbers;
    return 0;
}

字符串

完整的解决方案在本文底部

我花了几个小时来做这个，但我认为我有最佳的解决方案。谢谢你提供这个挑战。数字计算问题是我的一个爱好（错误）。

酒店地理位置

首先，我为这个问题发明了一些术语：

NQ或“非限定”。NQ数是指在其数字集合中既没有6也没有8的数。
Q6或“Qualified by 6”是任何在其数字集合中有6的数字，但没有8。
Q8或“Qualified by 8”是任何在其数字集合中有8的数字，但没有六。
PNQ或“永久不合格”。这是一个包含6或8的数字。

任何NQ数都可以通过简单地在其末尾附加6或8来变得合格。（例如，123是NQ，但1236是“合格”）
我之所以使用这个“限定”术语，是因为解决方案需要考虑将数字构建为从左到右的数字串。例如，一个非限定数，如123，可以简单地通过在其上附加6来变得限定。通过在123上附加6，该数字变为1236，并且是Q6。
任何合格的数字都可以通过附加一个6或8使其具有两个数字而永久不合格。例如，654是Q6，但如果我们在它上面附加一个8，它将永久不合格。任何附加在这个数字上的数字仍然会导致这个数字是PNQ。

慢解

所以让我们来介绍第一批代码。我上面讨论的正式枚举：

enum class NumberType : int
{
    NQ,    // NQ is "non-qualifying". It's a number with neither a six or an eight
    Q6,    // Q6 is "qualified by 6".  It's a number with at least a single six digit, but no eights
    Q8,    // Q8 is "qualified by 8".  It's a number with at least a single eight digit, but no sixes
    PNQ    // PNQ is "permanently non qualified". It's a number with both a six and an eight in it
};

字符串
让我们介绍一个帮助函数，它可以接受任何64位数字并告诉我们它是什么类型：

NumberType GetNumberType(uint64_t value)
{
    uint64_t sixCount = 0;
    uint64_t eightCount = 0;
    NumberType result = NumberType::NQ;
    while (value > 0)
    {
        uint64_t lastDigit = value % 10;
        value /= 10;
        if (lastDigit == 6)
        {
            sixCount++;
        }
        else if (lastDigit == 8)
        {
            eightCount++;
        }
    }
    if (sixCount && eightCount)
    {
        result = NumberType::PNQ;
    }
    else if (sixCount)
    {
        result =  NumberType::Q6;
    }
    else if (eightCount)
    {
        result = NumberType::Q8;
    }
    else
    {
        result = NumberType::NQ;
    }
    return result;
}

型
在这一点上，我们可以很容易地构建一个暴力解决方案来计算给定范围内Q6或Q8数字的计数。

uint64_t GetSixXorEightCount_BruteForceSlow(uint64_t start, uint64_t end)
{
     uint64_t count = 0;
     for (auto x = start; x <= end; x++)
     {
         NumberType nt = GetNumberType(x);
         count += ((nt == NumberType::Q6) || (nt == NumberType::Q8)) ? 1 : 0;
     }
     return count;
}

型
但是一旦我们开始进入一个有数十亿个数字的范围，那就不成比例了。

号码模式

我注意到了一些关于数字的事情。
取除零以外的所有个位数：

7 NQ号码（1，2，3，4，5，7，9）
1 Q6号码（6）
1 Q8号码（8）
PNQ 0

取10到99之间的所有两位数。如果你粗略地浏览一下这些数字，你会发现下面的统计数据是正确的：

56个NQ号码（例如23、45、79等）
16 Q6号码（60-67，69，16，26，36，46，56，76，96）
16个Q8号码（80-85，87-89，18，28，38，48，58，78，96）
2个PNQ编号（68和86）

要计算所有3位数的统计数据，你不必进行暴力搜索。你会意识到以下几点：

2位数范围内的所有NQ数都可以附加8位数中的一位来计算NQ集。因此，3位数的NQ总数仅为56*8。
所有的Q6和Q8号码都可以通过附加9位数中的一位来保持合格。此外，任何2位数范围内的NQ号码都可以通过简单地添加6或8来添加到Q6或Q8集合中。

因此，下面是一个通用的公式，用于计算任何一组N位数中有多少种数字：

countof_nq（N）== countof_nq（N-1）*8
countof_q6（N）== countof_q6（N-1）*9 + countof_nq（N-1）
countof_q8（N）== countof_q8（N-1）*9 + countof_nq（N-1）
countof_pnq（N）== countof_pnq（N-1）* 10 + countof_q6（N-1）+ countof_q8（N-1）

现在，如果问题空间是“计算N位数的计数与6或8”，那么递归函数将是容易的。但你如何计算范围内的数字在不同的数字边界？

分解示例

假设你想找到125和455之间的合格数字范围。
首先，通过截断数字，从125-455开始递归地分解问题。
首先求解12-45，这需要在此之前求解1-4。然后应用公式向上计数到下一个数字范围。但您必须添加一个修复步骤来取消计数不在范围内的数字（120-124和456-459）。

SolveFor(125-455):
    SolveFor(12-45)
       SolveFor(1-4) => {Q6:0, Q8:0, NQ: 4}
    Compute for 10-49 => {Q6: 4, Q8: 4, NQ: 32}
    Repair for 12-45 by uncounting 10,11,46,47,48,and 49 from the stats set => {{Q6: 3, Q8: 3, NQ: 28}
Compute for 120-459 => {Q6:55, Q8:55, NQ: 224}
Repair for 125-455 by uncounting 120-124 and uncounting for 456-459 => {Q6:54, Q8:54, NQ: 217}

型

最终解决方案

#include <iostream>
using namespace std;

enum class NumberType : int
{
    NQ,    // NQ is "non-qualifying". It's a number with neither a six or an eight
    Q6,    // Q6 is "qualified by 6".  It's a number with at least a single six digit, but no eights
    Q8,    // Q8 is "qualified by 8".  It's a number with at least a single eight digit, but no sixes
    PNQ    // PNQ is "permanently non qualified". It's a number with both a six and an eight in it
};

struct range_stats
{
    uint64_t nq;            // number of "non-qualifying numbers" that have neither 6 nor 8 in any digit
    uint64_t pnq;           // number of "permanently non-qualifying" numbers tht have both a 6 or 8
    uint64_t q6;            // number of qualifying numbers that have at least one occurance of 6, but not 8
    uint64_t q8;            // number of qualifying numbers that have at least one occurance of 8, but not 6
};

NumberType GetNumberType(uint64_t value)
{
    uint64_t sixCount = 0;
    uint64_t eightCount = 0;
    NumberType result;
    while (value > 0)
    {
        uint64_t lastDigit = value % 10;
        value /= 10;
        if (lastDigit == 6)
        {
            sixCount++;
        }
        else if (lastDigit == 8)
        {
            eightCount++;
        }
    }
    if (sixCount && eightCount)
    {
        result = NumberType::PNQ;
    }
    else if (sixCount)
    {
        result =  NumberType::Q6;
    }
    else if (eightCount)
    {
        result = NumberType::Q8;
    }
    else
    {
        result = NumberType::NQ;
    }
    return result;
}

void DeductStats(range_stats& stats, NumberType nt)
{
    switch (nt)
    {
        case NumberType::Q6:
        {
            stats.q6--; 
            break;
        }
        case NumberType::Q8:
        {
            stats.q8--;
            break;
        }
        case NumberType::NQ:
        {
            stats.nq--;
            break;
        }
        case NumberType::PNQ:
        {
            stats.pnq--;
            break;
        }
    }
}

void AddStats(range_stats& stats, NumberType nt)
{
    switch (nt)
    {
        case NumberType::Q6:
        {
            stats.q6++;
            break;
        }
        case NumberType::Q8:
        {
            stats.q8++;
            break;
        }
        case NumberType::NQ:
        {
            stats.nq++;
            break;
        }
        case NumberType::PNQ:
        {
            stats.pnq++;
            break;
        }
    }
}

void GetStatsForRange(uint64_t start, uint64_t end, range_stats& stats)
{
    // ASSUMES START AND END HAVE THE SAME NUMBER OF DIGITS

    if (end < 10)
    {
        uint64_t sum = 0;
        stats = {};
        for (auto i = start; i <= end; i++)
        {
            if (i == 6)
            {
                stats.q6++;
            }
            else if (i == 8)
            {
                stats.q8++;
            }
            else if (i > 0)
            {
                stats.nq++;
            }
        }
    }
    else
    {
        uint64_t newStart = start / 10;
        uint64_t newEnd = end / 10;
        uint64_t repairStart = (start / 10) * 10;   // convert 123 to 120
        uint64_t repairEnd = (end / 10) * 10 + 9;   // convert 567 to 569
        range_stats lowerStats = {};
        GetStatsForRange(newStart, newEnd, lowerStats);

        stats.nq = lowerStats.nq * 8;
        stats.q6 = lowerStats.q6 * 9 + lowerStats.nq;
        stats.q8 = lowerStats.q8 * 9 + lowerStats.nq;
        stats.pnq = lowerStats.pnq * 10 + lowerStats.q6 + lowerStats.q8;

        // now repair the stats by accounting for the ones that aren't in range
        for (uint64_t i = repairStart; i < start; i++)
        {
            auto nt = GetNumberType(i);
            DeductStats(stats, nt);
        }
        for (uint64_t i = repairEnd; i > end; i--)
        {
            auto nt = GetNumberType(i);
            DeductStats(stats, nt);
        }
    }
}

bool InRange(uint64_t value, uint64_t minimum, uint64_t maximum)
{
    return ((value >= minimum) && (value <= maximum));
}

bool IntersectionOfRanges(uint64_t levelStart, uint64_t levelEnd, uint64_t start, uint64_t end, uint64_t& newStart, uint64_t& newEnd)
{
    // ASSERT START <= END

    bool startInRange = InRange(start, levelStart, levelEnd);
    bool endInRange = InRange(end, levelStart, levelEnd);

    if ((end < levelStart) || (start > levelEnd))
    {
        return false; // no intersection
    }

    if (!startInRange && endInRange)
    {
        newStart = levelStart;
        newEnd = end;
    }

    else if (startInRange && endInRange)
    {
        newStart = start;
        newEnd = end;
    }
    else if (startInRange)
    {

        newStart = start;
        newEnd = levelEnd;
    }
    else
    {
        newStart = levelStart;
        newEnd = levelEnd;
    }
    return true;
}

void bruteForceTest(uint64_t start, uint64_t end, range_stats& stats)
{
    stats = {};
    for (auto i = start; i <= end; i++)
    {
        auto nt = GetNumberType(i);
        AddStats(stats, nt);
    }
}

uint64_t GetSixXorEightCount(uint64_t start, uint64_t end)
{

    range_stats stats = {};
    range_stats expected = {};
    range_stats results = {};

    if (start == 0)
    {
        start = 1;
    }

    if (start > end)
    {
        return 0;
    }

    uint64_t levelStart = 1;
    uint64_t levelEnd = 9;

    while (levelStart <= end)
    {
        uint64_t normalizedStart;
        uint64_t normalizedEnd;
        if (IntersectionOfRanges(levelStart, levelEnd, start, end, normalizedStart, normalizedEnd))
        {
            stats = {};
            GetStatsForRange(normalizedStart, normalizedEnd, stats);
            results.nq += stats.nq;
            results.q6 += stats.q6;
            results.q8 += stats.q8;
            results.pnq += stats.pnq;
        }

        levelStart = levelStart * 10;
        levelEnd = levelEnd * 10 + 9;
    }

    cout << "For the range of numbers between " << start << " and " << end << endl;
    cout << "Q6:  " << results.q6 << endl;
    cout << "Q8:  " << results.q8 << endl;
    cout << "NQ:  " << results.nq << endl;
    cout << "PNQ: " << results.pnq << endl;

    //cout << "Brute force computing expected" << endl;
    //bruteForceTest(start, end, expected);
    //cout << "Expected Q6:  " << expected.q6 << endl;
    //cout << "Expected Q8:  " << expected.q8 << endl;
    //cout << "Expected NQ:  " << expected.nq << endl;
    //cout << "Expected PNQ: " << expected.pnq << endl;

    return results.q6 + results.q8;
}

int main()
{
    uint64_t start = 0;
    uint64_t end = 0;

    cout << "Starting number:\n";
    cin >> start;
    cout << "Ending number:\n";
    cin >> end;

    uint64_t result = GetSixXorEightCount(start, end);

    std::cout << "There are " << result << " qualifying numbers in range that have a six or eight, but not both\n";

    return 0;
}

型

c++ 高效地找到给定范围内每个数字为6或8的数字

1条答案

相关问题

热门标签

最新问答