0
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ (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? $\endgroup$
    – greybeard
    Dec 22 '21 at 6:11
  • $\begingroup$ @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? $\endgroup$ Dec 22 '21 at 6:40
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    Dec 22 '21 at 7:03
  • $\begingroup$ 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? $\endgroup$ Dec 22 '21 at 7:30
  • 1
    $\begingroup$ [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$? $\endgroup$
    – greybeard
    Dec 22 '21 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.