## 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 10*n* + 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.

Pages: 1 2

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.

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