Given a number $n$, find $a$, such that digitSum($n-a$)+digitSum($a$) is maximum

Question

I saw this task in a programming competition, and I solved it, however, I just guessed the answer and don't know how to prove that it works.

As it turns out, to get the maximum, you have to make the number $a$ such that its digits 2nd through last are all nines, and the first digit of $a$ is (the first digit of $n$) - 1. (Parenthesis mean that we subtract 1 from the first digit, and not from $n$ itself).

For example:

$n$ is 2542, in that case $a$ is 1999.

Why does this work?

Answer 1

digitSum(n−a)+digitSum(a) should be

digitSum(n) + x*9 where x = number of carries in n-a

Finding the max value equal to finding Max(x), and Max(x) should be

digits(n) - 1

And "a" is not unique, for the example provided, all following "a" works:

 999, and 653, and 543

General answer is [0-1][5-9][4-9][3-9]

Answer 2

DISCLAIMER: This post is not entirely correct, since it misses a few special cases where $n_{i+1}=0$ which is possible if $a_{i+1}+b_{i+1}=0$ OR if $a_{i+1}+b_{i+1}+1=10$.

---

The goal is to find $a,b$ such that $$ a+b=n $$ and $\newcommand{\dsum}{\operatorname{digitSum}}\dsum(a)+\dsum(b)$ is maximal. Now write $$ \begin{align} a&=a_k...a_2a_1a_0 &&= 10^k a_k...100a_2+10a_1+a_0\\ b&=b_k...b_2b_1b_0 &&=10^k b_k...100b_2+10b_1+b_0 \\ n&=n_k...n_2n_1n_0 &&=10^k n_k...100n_2+10n_1+n_0 \\ \dsum(a)&=a_k+...+a_2+a_1+a_0 \\ \dsum(b)&=b_k+...+b_2+b_1+b_0 \end{align} $$ Each time we may have $a_i+b_i=n_i$ or possibly $a_i+b_i+1=n_i$ if $1$ was carried over from the last digit place, we may increase the sum of digitsums by $9$ if $n_{i+1}\geq1$ by increasing $a_i+b_i$ by $10$ and reducing $a_{i+1}+b_{i+1}$ by $1$.

The only digit places that prevents us from doing that will be those with $n_{i+1}=0$ which happens for the leading digit of $n$ for one OR if $n_i=9$ and we have no carries from the last place. If $n$ has other zero-digits, those will create exceptions too.