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.

About these ads

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

    Haskell.

    zeroes :: Integer -> Integer
    zeroes n | n < 10 = 0
    zeroes n = n' + zeroes n'
      where n' = n `div` 10

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: