问在给定的范围内有效地找到数字6×或8的每一个数字。

EN

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
};

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;
}

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;
}

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;
}