2
$\begingroup$

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?

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

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]

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.