Home > database >  Optimal solution to sum of digits problem
Optimal solution to sum of digits problem

Time:05-06

For a given number a, I have to find a number less than a (call it b) whose digit-sum plus b is equal to a. a can be a negative number.

Example:

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]

This is what I have so far but it's not efficient. Also, it doesn't work for odd single-digit numbers (it would have to output a decimal, i.e findB(1) = 0.5 because 0.5 0 .5 = 1). I tried to look for a pattern in i digitSum(i) but I couldn't figure it out. Is there a better way?

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;
}

CodePudding user response:

Positive decimal int has at most 10 digits. The sum of them can be at most 9 * 10 = 90. Just brute force looking for numbers between N-90 to N.

  • Related