Instantly share code, notes, and snippets.

# ericnormand/00 How many digits.md

Last active December 5, 2022 12:05
Show Gist options
• Save ericnormand/7174aaccc71025de86ddac77553f8595 to your computer and use it in GitHub Desktop.

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.

### nbardiuk commented Aug 29, 2022

```(defn pow10 [n]
(bigint (.pow (biginteger 10) n)))

(defn overlap [a-low a-high b-low b-high]
(max 0
(- (inc (min a-high b-high))
(max a-low b-low))))

(defn num-digits [low high]
(cond
(< (dec high) (inc low))
0

(< (dec high) 0)
(num-digits (.abs (biginteger high)) (.abs (biginteger low)))

(< low 0 high)
(+ (bigint 1) (num-digits 0 high) (num-digits 0 (.abs (biginteger low))))

:else
(->>
(for [digits (iterate inc 1)
:let [l (pow10 (dec digits))
h (dec (pow10 digits))]]
(* digits (overlap l h (inc low) (dec high))))
(drop-while zero?)
(take-while (comp not zero?))
(apply +))))

(deftest num-digits-test
(is (= 9      (num-digits 0 10)))
(is (= 180    (num-digits 9 100)))
(is (= 2700   (num-digits 99 1000)))
(is (= 36000  (num-digits 999 10000)))
(is (= 450000 (num-digits 9999 100000)))
(is (= 0      (num-digits 0 1)))
(is (= 1      (num-digits -1 1)))
(is (= 9      (num-digits -10 0)))
(is (= 180    (num-digits -100 -9)))
(is (= 379    (num-digits -100 100)))
(is (= 1688888888888888889 (num-digits 0 100000000000000000)))
(is (= 6.1777777777777776E32 (num-digits -10E30 10E30))))```

### jurjanpaul commented Aug 29, 2022

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

### hickst commented Aug 29, 2022

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

### jurjanpaul commented Aug 30, 2022

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

### jonasseglare commented Aug 30, 2022

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

### vpetruchok commented Aug 30, 2022

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

### miner commented Aug 30, 2022

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

### safehammad commented Aug 31, 2022

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

### arthurulacerda commented Dec 5, 2022

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