## Counting Zeros

### January 7, 2014

I’m not sure of the original source of today’s exercise; it feels like a Project Euler exercise — it’s mathy, it admits a simple but slow brute-force solution, and it also has a smart, fast solution — but I can’t find it there.

For a given

n, count the total number of zeros in the decimal representation of the positive integers less than or equal ton. For instance, there are 11 zeros in the decimal representations of the numbers less than or equal to 100, in the numbers 10, 20, 30, 40, 50, 60, 70, 80, 90, and twice in the number 100. Expectnto be as large as 10^{10,000}.

Your task is to write a program to count zeros. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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.