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

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?

• See also this other recent question – Jaap Scherphuis Oct 5 '18 at 13:32
• @JaapScherphuis I guess this guy took part in the same competition yesterday. lol – Coder-Man Oct 5 '18 at 13:35
• @JaapScherphuis: Cool, that is much more clear than what I contributed here! – String Oct 5 '18 at 13:40

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]

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.