这是question的链接。本质上，它要求查找数字总和为10的kth号。我尝试了多种解决方案，还在线查看了解决方案。具体来说，这个one(也在下面共享)。固定时间的人谈论算术级数中的离群值，并使用它来找到总和为10的nth号。显然，该代码是错误的，因为在k=1000等测试案例中失败。
#include <bits/stdc++.h>
using namespace std;
int findNth(int n)
{
int nthElement = 19 + (n - 1) * 9;
int outliersCount = (int)log10(nthElement) - 1;
// find the nth perfect number
nthElement += 9 * outliersCount;
return nthElement;
}
int main()
{
cout << findNth(5) << endl;
return 0;
}
最终，我最终写出算术级数+蛮力的组合，如下所示
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
int main() {
int n;
cin >> n;
int count = 0;
ll i = 19;
for (; ; i += 9) {
int curr = i;
int localSum = 0;
while (curr) {
localSum += curr%10;
curr /= 10;
}
if (localSum == 10) {
count += 1;
}
if (count == n) {
break;
}
}
cout << i << endl;
return 0;
}
我想知道，是否没有恒定时间或不需要我计算总和的更好算法，但是我的算法总是以我的数字总和为10的方式跳？
最佳答案
这是可以转换为C++的Python解决方案。
cached_count_ds_l = {}
def count_digit_sum_length (s, l):
k = (s, l)
if k not in cached_count_ds_l:
if l < 2:
if s == 0:
return 1
elif l == 1 and s < 10:
return 1
else:
return 0
else:
ans = 0
for i in range(min(10, s+1)):
ans += count_digit_sum_length(s-i, l-1)
cached_count_ds_l[k] = ans
return cached_count_ds_l[k]
def nth_of_sum (s, n):
l = 0
while count_digit_sum_length(s, l) < n:
l += 1
digits = []
while 0 < l:
for i in range(10):
if count_digit_sum_length(s-i, l-1) < n:
n -= count_digit_sum_length(s-i, l-1)
else:
digits.append(str(i))
s -= i
l -= 1
break
return int("".join(digits))
print(nth_of_sum(10, 1000))
这个想法是使用动态编程来找到给定最大长度和给定数字总和的数字。然后使用它在找到正确的数字的方式上舍弃整个数字块。
主要逻辑如下:
0 numbers of length 0 sum to 10
- need longer
0 numbers of length 1 sum to 10
- need longer
9 numbers of length 2 sum to 10
- need longer
63 numbers of length 3 sum to 10
- need longer
282 numbers of length 4 sum to 10
- need longer
996 numbers of length 5 sum to 10
- need longer
2997 numbers of length 6 sum to 10
- answer has length 6
Looking for 1000th number of length 6 that sums to 10
- 996 with a leading 0 sum to 10
- Need the 4th past 99999
- 715 with a leading 1 sum to 10
- Have a leading 1
Looking for 4th number of length 5 that sums to 9
- 495 with a leading 0 sum to 9
- Have a leading 10
Looking for 4th number of length 4 that sums to 9
- 220 with a leading 0 sum to 9
- Have a leading 100
Looking for 4th number of length 3 that sums to 9
- 55 with a leading 0 sum to 9
- Have a leading 1000
Looking for 4th number of length 2 that sums to 9
- 1 with a leading 0 sum to 9
- Need the 3rd past 9
- 1 with a leading 1 sum to 9
- Need the 2nd past 19
- 1 with a leading 2 sum to 9
- Need the 1st past 29
- 1 with a leading 3 sum to 9
- Have a leading 10003
寻找长度1的第一个数字，总和为6
-0，前导0和为6
-需要0的第1个
-0，前导1和6
-需要1点1分
-0，前导2和为6
-需要2点1分
-0，前导3和为6
-需要3点1分
-0，前导4和为6
-需要4点1分
-0，前5和为6
-需要5点1分
-1的前导6和为6
-领先100036
并在不到一秒的时间内完成。
顺便说一句，百万位是20111220000010，十亿位是10111000000002000000010000002100，万亿位是10000000100000100000100000000000001000000000000100000000010110001000。