Is there a quick way of figuring out the number of zeros of some number? It's easy for numbers like: $10$, $100$, $1000$, but not so obvious when the number is something like: $32546200234029402340324324035648445345341233567862040$. Is there an algorithm for solving this in less than linear time?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
An algorithm that ran in less than linear time wouldn't even be able to read all of its input. You would need an extremely problem-specific input encoding in order to be able to skip over any significant amount of input while being sure that the input you skip couldn't cause a zero to appear or disappear from the base-10 representation.
(But of course such a representation is possible. For example you can represent a string of decimal digits as a count of zeroes, followed by information about where the zeroes are, followed by the nonzero digits in their natural order).
There is no algorithm that can take as input the base-10 representation of a number and tell you how many zero digits it contains without examining each digit to see if it is a zero. This is no "easier" for a number like 1000 than it is for a number like 3254: until the algorithm has examined all the digits in the input, it can't know how many are zeroes.
It is at least conceivable that by representing the input in a different format one might produce an algorithm that runs in less than $O(n)$ time. However, this direction is unlikely to lead to anything useful. Henning Makholm's answer elaborates on this a little: if the representation of the input includes the count of zeroes explicitly, then there is an easy algorithm to count the zeroes: read in the count and emit it without reading the rest of the number. But this is of course pointless since you need to know the number of zeroes to produce such a representation in the first place.