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 num-digits [n m]
  "Very naive and slow! Fails for large ranges."
  (reduce + 
          (map (comp count str)
               (range (inc n) m))))

(pr (num-digits 0 1)) ;=> 0
(pr (num-digits 0 10)) ;=> 9
(pr (num-digits 9 100)) ;=> 180 (i.s.o. 179!)
(pr (time (num-digits 111 9999999)))

;; # Output
;; 0
;; 9
;; 180
;; "Elapsed time: 4625.000000 msecs"
;; 68888657
;; nil


;; (Edited and evaluated on my phone with 
;;  https://jurjanpaul.github.io/ape-cljs-playground)

(defn digstr [n m]
  (->>
    (drop 1 (range n m))
    (group-by #(count (str %)))
    (map (fn [cnt] (* (first cnt) (count (second cnt)))))
    (reduce + 0) ))

(defn num-digits [n m]
  (loop [x (inc n)
         sum 0
         length 1
         upper 10]
    (cond (>= x m) sum
          (< x upper)
          (let [new-x (min upper m)]
            (recur new-x
                   (+ sum (* length (- new-x x)))
                   length
                   upper))
          :else
          (recur x sum (inc length) (* 10 upper)))))

(pr (num-digits 0 1)) ;=> 0
(pr (num-digits 0 10)) ;=> 9
(pr (num-digits 9 100)) ;=> 180 (i.s.o. 179!)
(pr (time (num-digits 111 9999999)))
(pr (time (num-digits 111 9999999999999999)))


;; # Output
;; 0
;; 9
;; 180
;; "Elapsed time: 0.000000 msecs"
;; 68888657
;; "Elapsed time: 0.000000 msecs"
;; 158888888888888670
;; nil


;; (Edited and evaluated on my phone with 
;;  https://jurjanpaul.github.io/ape-cljs-playground)

Improving on previous.

(defn num-digits [n m]
  {:pre [(>= n 0) ; !! not at all assumed in challenge
         (< n m)]}
  (loop [x (inc n)
         sum 0
         length (count (str x))]
    (if (>= x m) 
      sum
      (let [delta (- (min m (js/Math.pow 10 length)) x)]
        (recur (+ x delta)
               (+ sum (* length delta))
               (inc length))))))

(defn num-digits [l u]
  {:pre [(<= l u)]}
  (cond
    (<= u 0) (num-digits (- u) (- l))
    (< l 0) (+ 1 (num-digits 0 (- l)) (num-digits 0 u))
    :default
    (loop [i 1
           result 0]
      (let [d (- u (max l (dec i)) 1)]
        (if (< 0 d)
          (recur (* 10 i) (+ result d))
          result)))))

(defn num-digits [m n]
  {:pre [(< m n)]}
  (->> (range (inc m) n)
       (map str)
       (map count)
       (apply +')))


(defn num-digits2 [m n]
  {:pre [(< m n)]}
  (loop [m (inc m)
         n (dec n)
         ret 0]
    (if (< n m)
      ret
      (recur (inc m) n (+' ret (count (str m)))))))

(require '[clojure.math :as m])

(defn num-digits [n m]
  #_ (assert (< n m))
  (let [n (inc n)]
    (if (and (< n 10) (<= m 10))
      (- m n)
      (loop [width (long (m/ceil (m/log10 (inc n))))
             p10w (long (m/pow 10.0 width))
             cnt (* (- p10w n) width)]
        (cond (= p10w m) cnt
              (< p10w m) (recur (inc width) (* p10w 10) (+ cnt (* (inc width) p10w 9)))
              :else (- cnt (* (- p10w m) width)))))))

Similar mathematical approach to previous ones, also performant for very large numbers, but with the arbitrary goal of avoiding loop. Like @miner it uses the shiny new clojure.math in Clojure 1.11:

(require '[clojure.math :as math])

(defn all-digits [n]
  (->> (inc n)
       (conj (mapv #(math/pow 10.0 %) (range (math/log10 (inc n)))))
       (partition 2 1)
       (map-indexed (fn [i [j k]] (* (- k j) (inc i))))
       (apply +)))

(defn num-digits [m n]
  (- (all-digits (dec n)) (all-digits m)))

Nice solution, @nbardiuk! It is very fast and also compact. I ran my code against your tests and got the same results as yours,
except for the large exponentiated value at the end.

My solution is too long to clutter this space, but if anyone is interested it is here. I also wrote quite a bit of documentation, and it also works with non-decimal bases.

Trying to achieve maximum speedup, and not being clever enough, I used boundary positions and classification of corner cases
together with multi-methods to prevent messy logic branching, end ended taking a crash course in hierarchies and dispatching.
This approach reminds me of a long ago business requirement document consisting of a table of 30 outcome scenarios , each with
a half-dozen conditions (columns). I had to implement in Java something similar to multi-methods, or be faced with a tangled mess
of if/else branches.

In this problem, the classification allows treating all similar ranges with a single operation, and the cost of dispatch is limited to
at most four calls per num-digits invocation. Here is a rough estimate with O(log N) performance:

time (dotimes [_ 25](num-digits -10e180 10e200)))
;;=> "Elapsed time: 11.012467 msecs"

Speaking of performance, I tried to find one-op formula for Summation( base^n X n) over a range but couldn't find one, although
there is one for base^n. If such a thing exists then num-digits is O(1), but without it I could only do O(log N), N being the largest
width from the boundaries.

Does anyone mathematically inclined know of that magic formula? Here is an implementation of sum-of-powers from this wikipedia article:

(require '[clojure.math :as m])

(defn pow [base p]
  (-> (m/pow (bigint base) (bigint p)) bigint))

(defn sop
  "Yields the sum of a(b^i) from i = 1 to i = n inclusive,
  a, b, n integers, and a >= 1, b >= 1 and n >= 0.
  See Closed-form formula ate:
  https://en.wikipedia.org/wiki/Geometric_series#Closed-form_formula
 "
[b a n]
(if (= 1 b)
  (* a (+ n 1))
  (* a 
     (/ (- 1 (pow b (+ n 1)))
        (- 1 b)))))

(defn bounded-sop
  "Yields the sum of a(b^from)...a(b^[to -1]),
  where from <= to and from > 0, both from and to integers"
 [b a from to]
  (- (sop b a to) (sop b a (dec from))))

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