We can prove that it is always possible to make ~N~ divisble by ~3~ by replacing some of its digits with ~3~'s: simply replace all of the digits with ~3~'s! For a ~D~ digit number, this will take ~D~ moves.

Okay, but we can obviously do better than that. How can we find the minimum number of replacements possible?

Well, there is a well-known divisibility rule for ~3~: a number is divisible by ~3~ if and only if the sum of its digits is divisible by ~3~ as well. Thus, we can reframe the question as finding the minimum number of integers in an array which must be replaced with ~3~'s to make the sum of the array divisible by ~3~.

Since we are working with divisbility by ~3~, we can take all digits modulo ~3~ and our new target is to achieve a sum which is congruent to ~0 \pmod 3~. Now, the only remaining values are ~0~, ~1~, and ~2~. Replacing a digit with a ~3~ is equivalent to replacing the digit with a ~0~, or simply deleting the digit.

If the sum of the digits of ~N~ is already congruent to ~0 \pmod 3~, ~N~ is already divisible by ~3~. Thus, the minimum number of replacements is simply ~0~.

Otherwise, let the sum of the digits of ~N~ be congruent to ~S \pmod 3~. If there exists a digit in ~N~ which is also congruent to ~S \pmod 3~, we can simply replace that digit with a ~3~, which effectively subtracts ~S~ from our sum. Now, the sum of the digits of ~N~ are congruent to ~0 \pmod 3~. Thus, in this case, the answer is ~1~ replacement.

If there does not exist a digit in ~N~ which is congruent to ~S \pmod 3~, then it turns out the answer is always ~2~. The proof of this is a little bit more tricky, and is left as an exercise to the reader.