Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
476 Eric Normand Newsletter

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

@nbardiuk
Copy link

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
Copy link

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
Copy link

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

@jurjanpaul
Copy link

jurjanpaul commented Aug 29, 2022

(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
Copy link

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
Copy link

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
Copy link

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
Copy link

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
Copy link

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

@KingCode
Copy link

KingCode commented Sep 12, 2022

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
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment