Remove some digits and re-order the digits (if necessary) so that the resulting integer would be the maximum possible integer that is divisible by 3.

Question

Given an integer. The task is to remove some digits and re-order the digits (if necessary) so that the resulting integer would be the maximum possible integer that is divisible by 3.

I am having some difficulties to think of an algorithm to implement it in code.

1. If the number is itself divisible by 3 then just print the digits in descending order.

2. If the number is 1 modulo 3 then remove one the smallest digit in the integer that is also 1 modulo 3 then just print the digits in descending order. If there is no such a digit then remove two smallest digits that are 2 modulo 3 then just print the digits in descending order. If there are no such digits neither then it is impossible to complete the task.

3. If the number is 2 modulo 3 then something similar to the case 2 above.

I was wondering if this algorithm is correct and optimal. Thanks in advance for your help.

Answer 1

You seem to be assuming that the integer is positive and that it’s written in decimal notation. If so, the algorithm is correct and optimal. The case where you write “it is impossible to complete the task” can’t occur, because the number can’t have residue $1$ modulo $3$ unless it contains either at least one digit with residue $1$ or at least two digits with residue $2$.

A problem that can occur, though, is that there are no digits left after you’ve removed some digits. In that case, it is indeed impossible to complete the task (unless we allow the empty digit string to represent $0$).

Answer 2

This algorithm is correct.

First, we can see that if the sum of the digits of a number is divisible by $3$, then the number itself will be divisible by $3$. Thus, once you have a number divisible by $3$, it is straightforward that you would have to arrange the digits in descending order to get the maximum value.

Now, all we need to focus on is which digits to remove to make the sum of digits divisible by $3$. If the number is already divisible by $3$, we can directly start the digit rearrangement process. If the number isn't divisible by $3$, your idea fails, and here is why...

Assume your number is $1 \bmod{3}$. If you have digits which are $1 \bmod{3}$, then your algorithm works since you have to remove the minimal number of digits, and here, you can remove just $1$ digit (you have to remove atleast $1$ digit). Clearly, this will be the smallest digit which is $1 \bmod{3}$.

But what if there are no digits which are $1 \bmod{3}$? You could have $3k-1$ digits which are $2 \bmod{3}$ and the rest of the digits to be $0 \bmod{3}$. One example is $223$. It is impossible to remove $1$ digit and make the number of divisible by $3$. Thus, you have to remove $2$ digits, and these will be the two smallest digits which are $2 \bmod{3}$. The existence of these digits is guarenteed since the number is $1 \bmod{3}$ and thus the number of digits which are $2 \bmod{3}$ is of the form $3k-1 \geqslant 2$.

The argument works symmetrically when your number is $2 \bmod{3}$ and there are no digits which are $2 \bmod{3}$. Remember that we consider the number as $0$ if you are forced to remove all the digits. This will only happen for $1$, $2$, $4$, $5$, $7$, $8$, $11$, $14$, $17$, $22$, $25$, $28$, $41$, $44$, $47$, $52$, $55$, $58$, $71$, $74$, $77$, $82$, $85$ and $88$. Just make sure that you print $0$ in the case these numbers are given as inputs.

NOTE : I assume you are only referring to positive numbers. If you want to replicate the process with negative numbers, just remove the negative sign as well :) and if that is cheating, you just have to make the number as small as possible. I leave this as an exercise to OP.