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 to n. 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. Expect n to be as large as 1010,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

Posted by programmingpraxis
Filed in Exercises
5 Comments »

5 Responses to “Counting Zeros”

  2. Sam said
    January 8, 2014 at 3:16 AM

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

  3. Paul said
    January 8, 2014 at 12:26 PM

    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
  4. joey said
    January 9, 2014 at 10:17 AM

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

  5. Josef Svenningsson said
    January 10, 2014 at 11:47 AM

    Haskell.

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

Leave a comment