Given a natural number n&lt;109, find the maximum number of the multiple of 3, which differs by exactly one digit from the given one

Question

Given a natural number n&amp;lt;109, find the maximum number of the multiple of 3, which differs by exactly one digit from the given one

sa3b4or9i9 · Accepted Answer

Step 1Let&amp;nbsp;n=∑k=0s−110kdk&amp;nbsp;be an s-digit number when written in base 10.Let&amp;nbsp;tc=&amp;nbsp;(∑k≠ck=0s−1dk)&amp;nbsp;bmod3&amp;nbsp;be the sum, modulo 3, of all the digits except the c&#039;th one.The algorithm goes:Set&amp;nbsp;c=s−1Step 2If digit&amp;nbsp;dc&amp;lt;9−tc, replace digit&amp;nbsp;dc&amp;nbsp;with&amp;nbsp;9−tc&amp;nbsp;and exitStep 3Set&amp;nbsp;c=c−1If&amp;nbsp;c≥0&amp;nbsp;return to Step 2.If&amp;nbsp;c&amp;lt;0&amp;nbsp;exit: there is no solution for this n.A few examples follow.n=523,&amp;nbsp;t2=2,&amp;nbsp;t1=2,&amp;nbsp;t0&amp;nbsp;Step 2&amp;nbsp;(c=2)&amp;nbsp;replaces the 5 with&amp;nbsp;9−2=7&amp;nbsp;and exits with 723n=826,&amp;nbsp;t2=2,&amp;nbsp;t1=2,&amp;nbsp;t0=1&amp;nbsp;Step 2&amp;nbsp;(c=2)&amp;nbsp;decides that the 8 is too big to be replaced. Step 2&amp;nbsp;(c=1)&amp;nbsp;replaces the 2 with&amp;nbsp;9−2=7&amp;nbsp;and exits with 876.n=879,&amp;nbsp;t2=1,&amp;nbsp;t1=2,&amp;nbsp;t0=0&amp;nbsp;. Step 2 decides that all the digits are too big to be replaced.&amp;nbsp;(8≥8,&amp;nbsp;7≥7,&amp;nbsp;9≥9). There is no solution for 879.

Given a natural number \(\displaystyle{n}{ < }{10}^{{{9}}}\),

Answered question

Answer & Explanation

New Questions in Pre-Algebra