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:
- 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$
- 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$?