Algorithm for the specific problem

A problem : Given a string of number in base $$10$$ we want an algorithm to calculate the number of numbers, where we replace (only) a single digit to produce a number so that that number is divisible by $$3$$.

example of input and output:

1. If the input is "23", the algorithm should produce an output $$7$$ since all the numbers satisfying the condition by replacing only $$1$$ digit at a time are $$03, 21, 24, 27, 33, 63, 93$$
2. If the input is "0081", the algorithm should produce an output $$11$$ since all the numbers satisfying the condition by replacing only $$1$$ digit at a time are $$0021, 0051, 0081, 0084, 0087, 0381, 0681, 0981, 3081, 6081, 9081$$

I would like to know if there exists an algorithm that is strictly less than the order of magnitude of $$O(n)$$, where $$n$$ is the number of digits of string.

If I use this algorithm, I have an $$O(n)$$ inference time.

algorithm: Loop for changing the string into list of digits, e.g. from "0023" >> [0,0,2,3]. Then, loop for each element in list and replace each with $$0$$ to $$9$$ and calculate the sum and check whether it is divisible by $$3$$ and count for the number that satisfies.

Is it possible to find such number with time $$O(1)$$ or $$O(f)$$ for some $$f=O(n^\epsilon)$$ for any $$\epsilon>0$$?

• (There is a much simpler algorithm for determining the count - start at the test for decimal numbers to be divisible by 9.) Assume that it was possible to ignore the last digit: Can you still provide the correct result? Dec 22 '21 at 6:11
• @greybeard Do you mean that if the input is "0023" and so $23\equiv 5 \pmod 9$? By ignoring the last digit we stille have the information that the last digit is $3$ since we are left with "002"? Can you explain more about such algorithm? What is the complexity of it? Dec 22 '21 at 6:40
• Both above comments/hints are entirely independent. For the first one, mod and congruence are right on track. The second one is about the conceivability of a (non-parallel) algorithm with a run time that grows slower than the number of digits. Dec 22 '21 at 7:03
• Can you provide the full algorithm? I don't know how to provide the result after ignoring the last digit and how slower it is? Dec 22 '21 at 7:30
• [W. Wongcharoenbhorn doesn't know how to provide the result after ignoring the last digit greybeard doesn't know how, too. But I think it obviously impossible. As there can't be an algorithm inspecting less than $n$ digits, what are the chances of a procedure in time $O(n^\epsilon), 0\le\epsilon\lt1$? Dec 22 '21 at 7:36