Delete as few as possible digits to make number divisible by 3

Question

I was solving this question, namely we have given number N, which can be very big, it can have up to 100000 digits.

Now I want to know what is the most efficient way to find those digits, and I think that in big numbers I will need to delete at most 3 digits to make the number divisible by 3.

I know that number is divisible by three if the sum of its digits is divisible by three, but I can't think of how can we use this.

My idea is to brute force over the string and to check if we delete that digit is the number going to be divisible by 3, but my solution fails at complex examples. Please give me some hints.

Thanks in advance.

Answer 1

If the sum of the digits modulo 3 is equal to 1, you want to delete a single 1, 4, or 7. If the sum of the digits is 2, you want to delete a single 2, 5, or 8.

If that can't be done, then you have to delete two digits.

To avoid scanning the list twice, you could remember the indices of up to two digits congruent to 1, and the indices of up to two digits congruent to 2, so when you compute the final modulus you know where to look.

Answer 2

The number 3 has some special properties relative to a base-10 number system that you can leverage.

10 is 1 more than 9, and 9 is evenly divisible by 3, so the "1" in "10" acts as a sort of remainder from adding 1 to 9. As a result, if the sum of all digits in the number is evenly divisible by 3 then that number is also divisible by 3.

So if you begin by figuring out what the modulo is after adding all the digits, then you'll know whether the number is divisible by zero (i.e. results in a modulo zero) or not. If not, then you can subtract one digit at a time, recalculating the modulo of the resulting number until you end up with a modulo of zero.

Answer 3

You should check what makes a number divisible by 3. If you find it you should divide the problem into smaller problems