数字和问题的最优解

Question

对于给定的数字 a，我必须找到一个小于 a 的数字（称之为 b），其数字和加上 b 等于a。 a 可以是负数。

示例：

findB(41)        = 34, [34 + 3 + 4 = 41]
findB(-145)      = -140, [-140 + (-1) + (-4) + 0 = -145]
findB(14)        = 7, [7 + 7 = 14]
findB(11)        = 10, [10 + 1 + 0 = 11]
findB(-101)      = 100, [-100 + (-1) + 0 + 0 = -101]
findB(458962713) = 458962758, [458962758 + 4 + 5 + 8 + 9 + 6 + 2 + 7 + 5 + 8 = 458962713]

这是我目前所拥有的，但效率不高。此外，它不适用于奇数个位数（它必须输出小数，即 findB(1) = 0.5 因为 0.5 + 0 + .5 = 1）。我试图在 i + digitSum(i) 中寻找模式，但我无法弄清楚。有没有更好的方法？

int digitSum(int num) {
  int sum = 0;
  while (num) {
    sum += num % 10;
    num /= 10;
  }
  return sum;
}

int findB(int a) {
  for (int i = 1; i < abs(a); i++) {
    int sum = a < 0 ? i - digitSum(-i) : i + digitSum(i); 
    if (sum == a)
        return i;
  }
  return -1;
}

Answer 1

正小数int最多有10位。它们的总和最多可以是9 * 10 = 90。只是蛮力寻找N-90到N之间的数字。

数字和问题的最优解

Optimal solution to sum of digits problem

c

algorithm