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.

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 600 other followers

%d bloggers like this: