只有2和5为数字的特殊数字

Question

特殊数是指仅由2和5组成的数字，例如-2、5、22、25、52、555等。函数f(k)返回大于或等于k的最小数，是一个特殊数。

我的问题是，如果有两个数字L和R，我们需要找到f(k)的和，其中L<=k<=R。我在c++中求解它的方法如下：

#include <bits/stdc++.h>
using namespace std;

long long int power(long long int a, long long int b)
{
    long long int prod = 1;
    for (long long int i = 1; i <= b; i++)
        prod *= a;
    return prod;
}

long long int f(long long int k)
{
    long long int nod = 0;
    long long int temp = 0, carry = 0;
    while (k)
    {
        if (k == 1)
        {
            temp = 0;
            for (int i = nod; i >= 0; i--)
                temp = temp * 10 + 2;
            return temp;
        }
        if (((k % 10) + carry) <= 2)
        {
            temp = 2 * power(10, nod) + temp;
            carry = 0;
        }
        if (((k % 10) + carry) > 2 && ((k % 10) + carry) <= 5)
        {

            temp = 5 * power(10, nod) + temp;
            carry = 0;
        }
        if (((k % 10) + carry) > 5 && ((k % 10) + carry) <= 9)
        {
            temp = 2 * power(10, nod) + temp;
            carry = 1;
        }
        k = k / 10;
        nod++;
    }

    if (carry == 1)
        temp = 2 * power(10, nod) + temp;

    k = temp;
    return k;
}

int main()
{
    long long int t;
    cin >> t;
    while (t--)
    {
        long long int l, r;
        cin >> l;
        cin >> r;
        long long int sum = 0;
        for (long long int i = l; i <= r; i++)
            sum += f(i);
        cout << sum << endl;
    }
    return 0;
}

但是它并没有像预期的那样工作，而且对于许多测试用例来说，它超过了时间限制。什么是解决这个问题的正确和最优的方法？

这个问题来自于黑客世界。

https://www.hackerearth.com/pt-br/problem/algorithm/ozs-cool-numbers-a97d4b77-4f0585e3/#:~:text=Special%20numbers%20are%20positive%20integers,n%20d%20265%20are%20not.&text=For%20each%20test%20case%2C%20print%20the%20required%20answer.&text=Time%20Limit%3A%201%2C0%20sec,s)%20for%20each%20input%20file.

Answer 1

我试过了，而且似乎成功了。有待同行审查。

一般的方法是在起始数的基础上找到一个最小的特殊数字，然后把这个特殊的数字乘以数字的数量，直到你到达下一个特殊的数字。由于两个特殊数字之间的每一个数字都将映射到相同的特殊数字，因此您只需计算每个特定数字一次。

一个64位的无符号整数可以表示一个十进制数，它由最多19位数的2s和5s组成。因此，下一个特殊数字的每一个搜索在输入数字中的十进制数中都是对数(基数2)。和循环的迭代次数在输入数的十进制数中也是对数(基数2)，使总复杂度O(log 2N)。

将sum = 0

• Given设置为起始数L，将next_k = L

• Find设置为最小的特殊数字，不小于next_k；special = f(next_k)

• Set k = next_k

• Set next_k = min(special, R) + 1。这是使用在iterations

• Set distance = next_k - k

• sum = sum + distance * special

• If next_k <= R中常见的一遍结束成语，然后转到3.

• Done.返回sum.

当然，如何在给定的k之上“安装”一系列2s和5s的问题需要回答。我的方法是从最大系列的小数点5开始，它可以用64位表示(连续19位)。

1. 将此5掩码向下移动10倍，直到与输入数字
2. 的宽度相同时，从最重要的数字开始迭代，并测试将该数字设置为2是否仍然“符合”输入数字。如果是的话，就绕着它转。--

/*
A special number is a decimal number such that its
digits are only 2 or 5, e.g. {2, 5, 22, 25, 52, 55, ...}

Write a function, f( ), for any non-special number, k, that returns
the smallest special number that is greater than or equal to k

Given a range [L, R], find the sum of all f(k) for each k such
that L <= k <= R
*/

#include <algorithm>
#include <iomanip>
#include <iostream>

using value_t = unsigned long long;
static constexpr value_t MAX_FIVES = 5'555'555'555'555'555'555ull;
static constexpr value_t MAX_THREE_MASK = 3'000'000'000'000'000'000ull;

value_t least_special_no_less_than(value_t k)
{
    value_t special_number = MAX_FIVES;
    value_t three_mask = MAX_THREE_MASK;

    if (k == 0)
    {
        special_number = 2;
    }
    else
    {
        // shift the 555... mask down as low as it can go
        while (special_number / 10 >= k)
        {
            special_number /= 10;
            three_mask /= 10;
        }

        // twiddle each digit from 5->2 to fit the sheet onto the bed
        while (three_mask)
        {
            if (special_number - three_mask >= k)
                special_number -= three_mask;

            three_mask /= 10;
        }
    }

    return special_number;
}

int main()
{
    std::cout << "A special number is one with digits only 2 or 5, e.g. {2, 5, 22, 25, 55, 222, ...}\n"
        << "For a number, k, f(k) returns the lowest special number gte k\n"
        << "Enter two numbers L and R, this program calculates sum(f(k)) for all k s.t. L <= k <= R\n"
        << "\n"
        << "Enter L followed by R: ";

    value_t L, R;
    std::cin >> L >> R;

    value_t sum = 0;
    value_t k, next_k = L;
    std::cout << std::right
        << std::setw(20) << "k" << " "
        << std::setw(20) << "next_k" << " "
        << std::setw(20) << "special" << " "
        << std::setw(20) << "running sum" << " "
        << "\n";
    do
    {
        value_t special = least_special_no_less_than(next_k);
        k = next_k;
        next_k = std::min(special, R) + 1;

        sum += (next_k - k) * special;

        std::cout
            << std::setw(20) << k << " "
            << std::setw(20) << next_k << " "
            << std::setw(20) << special << " "
            << std::setw(20) << sum << " "
            << "\n";
    } while (next_k <= R);

    std::cout << std::left
        << "\nSum of all special numbers between [" << L << ", " << R << "]: "
        << sum << "\n";
}

这给出了以下示例输出：

A special number is one with digits only 2 or 5, e.g. {2, 5, 22, 25, 55, 222, ...}
For a number, k, f(k) returns the lowest special number gte k
Enter two numbers L and R, this program calculates sum(f(k)) for all k s.t. L <= k <= R

Enter L followed by R: 12 47
                   k               next_k              special          running sum
                  12                   23                   22                  242
                  23                   26                   25                  317
                  26                   48                   52                 1461

Sum of all special numbers between [12, 47]: 1461

Answer 2

要找到至少等于给定数字的下一个特殊数字，我将提取该数字的十进制数。然后从最高阶数字开始：

• ，如果一个数字大于5，那么这个数字和下面所有的数字都会值2，并且前面的数字应该增加(如果前面是5，我们需要迭代，如果我们是第一个数字，我们需要添加一个新的数字)，如果一个数字是5时，保持它并继续到下一个
• (如果是3或4时)，这个值将是5，下面所有的数字都将是2
• ，如果是2，则保留它并继续到下一个
• ，如果0或1，这一个和下面的数字将是2H 210f 211>f 211

出于效率原因，我会计算这个数字，在当前数字小于或等于的情况下将其相加，然后通过增加其最小有效数字来计算下一个特殊数字。

在下面的代码中，我选择将所有特殊数字处理封装在一个包含数字值向量和数字本身的类中：

#include <vector>
#include <iostream>

class Special {
public:

    long val;
    std::vector<char> digits;

    // ctor builds first special number at least equal to val       
    Special(long val) {

        std::vector <char> d;
        int n=0;
        while (val > 0) {                // extract all decimal digits
            d.push_back(val % 10);
            val /= 10;
            n++;
        }
        digits = std::vector<char>(n, 2); // initialize the special number with 2
        // and start processing starting from most significant digit
        while (n-- > 0) {
            if (d[n] > 5) {
                digits[n] = 6;
                normalize(n);
                return;
            }
            else if (d[n] > 2) {
                digits[n] = 5;
                if (d[n] != 5) {
                    normalize(digits.size());
                    return;
                }
            }
            else {
                digits[n] = 2;
                if (d[n] != 2) {
                    normalize(digits.size());
                    return;
                }
            }
        }
        normalize(digits.size());
    }
    Special& normalize(int n) {
    /* compute the binary value, and process carries starting from nth digit */
        // First process carries
        int ndigits = digits.size();
        while (n < ndigits) {
            if (digits[n] > 5) {
                digits[n] = 2;
                if (n == ndigits - 1) {
                    digits.push_back(2);
                }
                else {
                    digits[n+1] += 1;
                }
            }
            else {
                if (digits[n] > 2) {
                    digits[n] = 5;
                }
                else {
                    digits[n] = 2;
                }
                break;
            }
            n++;
        }
        // compute the binary value
        val = 0;
        for (auto ix=digits.rbegin(); ix!= digits.rend(); ix++) {
            val = 10 * val + *ix;
        }
        return *this;
    }
    Special& next() {
        /* increase to next special number */
        digits[0] += 1;       // just increase least significant digit
        return normalize(0);  // and normalize
    }
};

int main() {
    // read N
    int N;
    std::cin >> N;
    long l,r, tot;
    for (int i=0; i<N; i++) {
        std::cin >> l >> r;
        tot = 0;
        Special s(l);
        while(l <= r) {
            if (l > s.val) s.next();
            tot += s.val;
            l += 1;
        }
        std::cout /* << l << " - " << r << " : " */ << tot << '\n';
    }
    return 0;
}

Answer 3

，也许很晚了，但我要留在这里，

对于这个问题，关键是要认识到这个系列是如何工作的。只有两个位数，即2和5，这意味着该系列将表现为

225

• ...

• n

• 2->创建22和25

• 5

下面是我为进一步提高效率而使用堆栈解决问题的实现：

long long nthNiceNumber(int n) 
{
    queue<long long> q;
    q.push(2);  // init the stack with 2 and 5
    q.push(5);
    
    int nE = 2;    // means the back of the queue is the n^th element
    while (nE < n) // while doesn't reach the n^th element
    {
        q.push(q.front() * 10 + 2);
        nE++;
        
        if (nE == n) break;   // in one iteration, the queue will have 2 new 
                              // element,so if the first element appended is enough, break
        
        q.push(q.front() * 10 + 5);
        nE++;
        
        q.pop(); // pop the front of the queue that used to create two new element above, since it doesn't relevant anymore
    }
    int size = q.size();
    while (size-- > 1) q.pop(); // the n^th element always at the end of the queue, so pop until only one element left.
    return q.front();
}