令 N 为整数。如果 N = 2536，则反向 N 为 6352。如果 N = 1000000，反向 N 为 1。
我们得到一个整数 M，其中 1 我们需要找到一个整数 N 是否存在，其中 N + reversed(N) = M。
除了蛮力之外，还有什么想法吗？
最佳答案
这里我将简要描述一个算法。需要注意的是，很多细节需要填写。
基本思想是看 M 的第一位和最后一位来确定 N 的第一位和最后一位之和，然后从 M 中减去这个数量，以减少到更短的数字的情况。
如果一个数字可以写成 N + reverse(N) ，我们就称它为 好 。
(编辑:在实现中，人们可能需要一个函数 IsGood(M, k) 来判断 M 是否可以写为 N + reverse(N) 一些 N < 10^k 。但让我们暂时跳过这个细节。)
确定给定数字 M 是否好的算法如下:c 和 d 是 M 的第一位和最后一位，R 是中间部分。也就是说， M 具有数字表达式 cRd 。
有两种情况:
c 不等于 1 c 等于 1 在
c 不等于 1 的情况下，数字 c 不能是进位。这是 正常情况 。现在看看 d 。如果
d 等于 c ，则 M 是好的当且仅当 R 是好的。如果
d 等于 c - 1 ，则存在从 R 到 c 的进位，因此 M 是好的当且仅当 1R 在 携带案例 中是好的(见下文)。如果
d 等于其他任何值，则 M 不好。在
c 等于 1 的情况下，还有可能 c 是进位。设
e 为 R 的第一位，将 M 写为 1eTd 。如果
d = 9 或 e < d ，则无法携带手提箱。(编辑:这是错误的，如果
d = 9 的情况下 e = 0 是可能的。)否则，当且仅当
(e - d)(T - 1) 良好时，手提箱是可能的。如果手提箱保持或正常情况下保持，那么
M 是好的。例子:
让我们从
M = 12001 开始。由于
c = 1 ，有正常情况和携带情况。在正常情况下，我们有
d = 1 ，所以我们需要测试 200 是否好。对于 M = 200 ，我们有 c = 2 和 d = 0 ，所以 200 的数字不好，因此 M = 12001 的正常情况失败。在carry的情况下，我们需要测试
(12001 - 11000 - 11) / 10 = 99是否好。对于 M = 99 ，我们有 c = 9 和 d = 9 ，所以这又归结为 0 是否好，这显然是正确的。因此，手提箱是固定的。结论是
M 是好的。时间复杂度:
通过一些详细的论据(我不想在这里介绍)，可以证明该算法在
O(log_10(M)) 时间运行。关于algorithm - 找到整数 N，加上它的(十进制)反向，等于 M，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36916065/