476 Eric Normand Newsletter

00 How many digits.md

How many digits?

Imagine you took all the integers between n and m (exclusive, n < m) and concatenated them together. How many digits would you have? Write a function that takes two numbers and returns how many digits. Note that the numbers can get very big, so it is not possible to build the string in the general case.

Examples:

(num-digits 0 1) ;=> 0 (there are no integers between 0 and 1)
(num-digits 0 10) ;=> 9 (1, 2, 3, 4, 5, 6, 7, 8, 9)
(num-digits 9 100) ;=> 180

UPDATE: My original example was wrong. The last one should return 180, not 179. It was my fault, due to off by one errors.

Thanks to this site for the problem idea, where it is rated Expert in Python. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://ericnormand.me/newsletter

(defn exp [x n]
  (reduce * (repeat n x)))
​
(defn num-digits
  [n m]
  (loop [n-digits 0
         order    1]
    (let [prev-exp-order  (exp 10 (dec order))
          curr-exp-order  (exp 10 order)
          higher-in-order (min m
                               curr-exp-order)
          lower-in-order  (min (max (inc n)
                                    prev-exp-order)
                               curr-exp-order)]
      (if (> prev-exp-order m)
        n-digits
        (recur (+ n-digits
                  (* order
                     (- higher-in-order
                        lower-in-order)))
               (inc order))))))