论坛 › 数据结构与算法 › 求1到n的数位和，要求O(n)的复杂度

lsmCC 发表于 2024-2-20 00:06:23

求1到n的数位和，要求O(n)的复杂度

#include <iostream>
using namespace std;

int f(int n)
{
    string str = to_string(n);
    int sum_1 = 0;
    for (char ch : str) {
      sum_1 += ch - '0';
    }
    return sum_1;
}

void solve()
{
    long long n;
    cin >> n;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
      sum += f(i);
    }
    cout << sum << endl;
}参考代码如下

int main()
{
    int t;
    cin >> t;
    while (t--) {
      solve();
    }
    return 0;
}

FishC 发表于 2024-2-20 00:06:47

题目要求计算从1到n的数位和，要求复杂度为O(n)。下面是一个符合要求的解法。

首先，我们可以观察到从1到n的每个数字的数位和都是从1到n最高位的数位和的累加。例如，从1到100的数位和等于从1到99的数位和加上100的数位和。因此，我们可以使用动态规划来解决这个问题。

具体的步骤如下：

1. 创建一个长度为n+1的数组sums，用来存储从1到n的每个数字的数位和。
2. 初始化sums为0。
3. 从1到n，遍历每个数字i：
   a. 获取数字i的最低位digit：digit = i % 10。
   b. 更新数字i的数位和为sums = sums + digit。
4. 返回sums作为结果。

下面是对应的C++代码：

#include <iostream>
#include <vector>
using namespace std;

int getDigitSum(int n) {
    vector<int> sums(n+1, 0);
    for (int i = 1; i <= n; i++) {
      int digit = i % 10;
      sums = sums + digit;
    }
    return sums;
}

int main() {
    int n;
    cout << "请输入一个整数n：";
    cin >> n;
    int result = getDigitSum(n);
    cout << "从1到" << n << "的数位和为：" << result << endl;
    return 0;
}

这段代码中，我们首先定义了一个名为getDigitSum的函数，用来计算从1到n的数位和。在主函数中，我们输入一个整数n，并调用getDigitSum函数来计算结果，然后输出结果。

希望对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

zhangchenyvn 发表于 2024-2-20 12:01:12

1:将数字转换成str
2:数一下位数（strlen）
3:输出45*1+45*11+45*111+…+45*111（strlen个1）111
4:试一下！！

zhangjinxuan 发表于 2024-2-24 09:57:58

本帖最后由 zhangjinxuan 于 2024-2-24 10:00 编辑

严格来说不会有 $O(n)$ 的时间复杂度，这个代码还是 $O(n \log_{10} n)$ 的复杂度。

不过你可以使用数位DP将时间复杂度做到 $O(\log_{10} n)$，虽然并不是楼主需要的 $O(n)$，但是这个算法比 $O(n)$ 算法优秀得多，可以解决 $n=10^{18}$ 甚至更大的情况。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int d, m;
long long l, r;

struct Info {
        int a, numtot;
        const Info operator + (const Info &i) const {
                Info res = {{}, numtot + i.numtot};
                for (int j = 0; j <= 9; ++j) res.a = a + i.a;
                return res;
        }
        const Info operator - (const Info &i) const {
                Info res = {{}, numtot - i.numtot};
                for (int j = 0; j <= 9; ++j) res.a = a - i.a;
                return res;
        }
} f;

Info calc(int i, int zero, int limited) {
        if (i == m + 1) return {{}, zero};
        if (f.numtot != -1) return f;
        Info res = {{}, 0};
        if (i == 1) {
                for (int j = 0; j <= d; ++j) {
                        Info tmp = calc(i + 1, (j != 0), (j != d));
                        res = res + tmp;
                        if (j != 0) {
                                res.a += tmp.numtot;
                        }
                }
        } else {
                if (limited) {
                        for (int j = 0; j <= 9; ++j) {
                                Info tmp = calc(i + 1, (bool)(zero | j), 1);
                                        res = res + tmp;
                                if ((bool)(zero | j)) {
                                res.a += tmp.numtot;
                                }
                        }
                } else { // ???üì? 0 ~ d μ?????￡?2￠?ú×?òa?ó
                        for (int j = 0; j <= d; ++j) {
                                Info tmp = calc(i + 1, (bool)(zero | j), (j != d));
                                        res = res + tmp;
                                if ((bool)(zero | j)) {
                                res.a += tmp.numtot;
                                }
                        }
                }
        }
        return f = res;
}

signed main() {
    int t = 1;
        while (t--) {
            l = 1;
          scanf("%lld", &l, &r);
                m = 0;
                for (long long tr = r; tr; tr /= 10)
                        d[++m] = tr % 10;
                for (int i = 1, j = m; i < j; ++i, --j) swap(d, d);
                for (int i = 0; i < 21; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) f.numtot = -1;
                Info tmp = calc(1, 0, 0);
                if (l != 1) {
                        m = 0;
                        memset(d, 255, sizeof(d));
                        for (long long tr = l - 1; tr; tr /= 10)
                                d[++m] = tr % 10;
                        for (int i = 1, j = m; i < j; ++i, --j) swap(d, d);
                for (int i = 0; i < 21; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) f.numtot = -1;
                        tmp = tmp - calc(1, 0, 0);
                }
                long long res = 0;
                for (int i = 1; i <= 9; ++i) res += tmp.a * i;
                printf("%lld\n", res);
        }
//        printf("%lld\n", tmp.numtot);
        return 0;
}
/*
01
*/

查看完整版本: 求1到n的数位和，要求O(n)的复杂度