I have an algorithm to solve this problem * given a natural number $n< 10^{9},$ find the maximum number of a multiple of $3,$ which differs by exactly one digit from the given one." My algorithm is finding $m= n\mod 3.$ Then I will check from the left from the first digit, i.e. $i,$ if that at least $9- m,$ I must continue with the next digit, so on.. Else if $i< 9- m,$ substracting $i:=i- m,$ then adding $i:=i+ 3,$ not until $i> 9.$ But it seems not good.
And my algorithm is wrong by tested, how can I fix it up, I need to the help, thanks for all your comments !
Your algorithm takes the whole of $n$ modulo $3$ into account. You need to take "$n$-each digit $\bmod 3$" into account. See my definition of $t_c$ below.
Let $\displaystyle n = \sum_{k=0}^{s-1}10^kd_k$ be an $s$-digit number when written in base $10$.
Let $\displaystyle t_c = \large (\sum_\stackrel{k=0}{k \neq c}^{s-1}d_k \large ) \bmod 3$ be the sum, modulo $3$, of all the digits except the $c$'th one.
The algorithm goes:
Step $1$
Set $c=s-1$.
Step $2$
If digit $d_c \lt 9-t_c$, replace digit $d_c$ with $9-t_c$ and exit.
Step $3$
Set $c=c-1$.
If $c \ge 0$ return to Step $2$.
If $c < 0$ exit: there is no solution for this $n$.
A few examples follow.
$n=523, t_2=2, t_1=2, t_0=0$. Step $2$ ($c=2$) replaces the $5$ with $9-2=7$ and exits with $723$.
$n=826, t_2=2, t_1=2, t_0=1$. Step $2$ ($c=2$) decides that the $8$ is too big to be replaced. Step $2$ ($c=1$) replaces the $2$ with $9-2=7$ and exits with $876$.
$n=879, t_2=1, t_1=2, t_0=0$. Step $2$ decides that all the digits are too big to be replaced. ($8 \ge 8, 7 \ge 7, 9 \ge 9$ ). There is no solution for $879$.