Counting Zeros
January 7, 2014
The brute-force solution splits each number up to n into digits and counts the zeros:
(define (count-zeros num)
(let loop ((num num) (count 0))
(if (zero? num) count
(let ((zeros (length (filter zero? (digits num)))))
(loop (- num 1) (+ count zeros))))))
> (count-zeros 100)
11
A better solution is recursive. If you know the number of zeros up to n, then the number of zeros up to 10n + 9 can be computed easily; each zero is repeated ten times, plus there are an additional n + 1 zeros in the least significant position. Then it is only necessary to subtract the 9 – c zeros for those numbers that don’t end in 0:
(define (count-zeros num)
(let loop ((f 0) (z 0) (n 0) (ns (digits num)))
(if (null? ns) f
(loop (+ (* 10 f) n (- (* z (- 9 (car ns)))))
(if (zero? (car ns)) (+ z 1) z)
(+ (* 10 n) (car ns)) (cdr ns)))))
> (count-zeros 1000000000000)
1088888888901
The input is considered left-to-right, z is the number of zeros in the portion of the input that has already been considered, n is the number that has so far been considered (the actual number itself, so after two recursive calls on the input number 1000000000000, n is 10), and f is the accumulating result.
Because the number of zeros grows quickly, and n may be large, it is convenient to provide a version of the counting function that returns the result modulo some constant:
(define (count-zeros num m)
(let loop ((f 0) (z 0) (n 0) (ns (digits num)))
(if (null? ns) f
(loop (modulo (+ (* 10 f) n (- (* z (- 9 (car ns))))) m)
(if (zero? (car ns)) (+ z 1) z)
(+ (* 10 n) (car ns)) (cdr ns)))))
> (count-zeros (expt 10 10000) (next-prime 12345678910))
2646381410
Digits is from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/6p99jesa.
In Python…
http://ideone.com/wCLHa2
Never mind that; it doesn’t work perfectly. I’ll fix it up.
In Python. Method is from here.
def number_of_zeros(n): Z = N = F = 0 for sdigit in str(n): digit = int(sdigit) F = 10 * F + N - Z * (9 - digit) if digit == 0: Z += 1 N = 10 * N + digit return F(define (count-one n)
(cond ((= n 0) 1)
((< n 10) 0)
(else
(+ (count-one (mod n 10))
(count-one (div n 10))))))
(define (count-from-one i n)
(if (< n 10)
i
(count-from-one (+ i (count-one n))
(- n 1))))
(begin
(display (count-from-one 0 100))
(newline))
Haskell.