Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Your question implies that you think that the number of zeroes in a number like 1000 can be calculated in less than linear time. If you do think that, can you please explain how you think it can be done? –  MJD Feb 20 '13 at 14:35
    
@MJD - I think he means linear in the number itself $O(n)$, not in the number of digits $O(\log(n))$ –  nbubis Feb 20 '13 at 14:36
    
I mean linear in the number of digits. Look at every digit, if it's equal to zero increment the count, otherwise pass. –  saadtaame Feb 20 '13 at 14:37
2  
@nbubis That is ridiculous. If you have an $O(\log n)$ method then you automatically have an $O(n)$ algorithm by definition. And obviously there is an $O(\log n)$ algorithm for counting the number of zeroes, namely, to scan the digits and count the zeroes. –  MJD Feb 20 '13 at 14:38
    
In a computer, the number will be stored in binary. If you want the number of zeros in base 10, you will have to convert first. Scanning the number in binary can be done, as well. –  Ross Millikan Feb 20 '13 at 14:43

2 Answers 2

up vote 3 down vote accepted

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).

share|improve this answer
    
If it can't be done in general. How can we prove it? –  saadtaame Feb 20 '13 at 15:10
    
My second paragraph says it can be done by choosing a sufficiently strange input encoding. But then again when we're talking about sublinear running times, an input encoding that strange would usually be considered to define a different problem. So in order to produce a rigorous proof that there's no sublinear algorithm, you'd have to start by defining exactly how the input to this algorithm is to be encoded. –  Henning Makholm Feb 20 '13 at 15:12
    
You say it may be possible for problem-specific input. I mean what about general input. We don't assume anything about the input distribution. –  saadtaame Feb 20 '13 at 15:14
    
@saadtaame: I'm not talking about distributions, but about the encoding of the input to the algorithm. How does the input number get presented to the algorithm as a string of symbols from a finite alphabet? –  Henning Makholm Feb 20 '13 at 15:19
    
Let's agree that the input is encoded as a string of characters. –  saadtaame Feb 20 '13 at 15:20

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.