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.

Pages: 1 2

5 Responses to “Counting Zeros”

1. Sam said

Never mind that; it doesn’t work perfectly. I’ll fix it up.

2. Paul said

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
```
3. joey said

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

4. Josef Svenningsson said

``````zeroes :: Integer -> Integer