478 Eric Normand Newsletter

00 Super Digit.md

Super Digit

This is kind of a contrived problem, but it's the kind that breeds lots of interesting implementations and tests your understanding of lower-level details. So let's do it!

You're given an integer n and an integer k. There is an integer p that is k instances of the digits of n concatenated together. For example:

n=123, k=3 -> p=123123123
n=32, k=6 -> p=323232323232
n=24543, k=125 -> p=245432454324543245432454324543...

Now, take that number p and find its superdigit. The superdigit is defined as follows:

superdigit(d) = d                             if # of digits = 1
superdigit(d) = superdigit(sum(digits of d))  otherwise

That is, if the number has one digit, the superdigit is the number. (Example: superdigit(4)=4). Otherwise, sum the digits and take the superdigit of the result. (Example: superdigit(23)=superdigit(2+3)=5).

Your task is to write a function that calculates the superdigit of n and k.

Examples

;           n  k
(superdigit 1  1) ;=> 1
(superdigit 10 2) ;=> 2
(superdigit 11 3) ;=> 6
(superdigit 38 7) ;=> 5
(superdigit 38789789374294723947328946 1000000000000000) ;=> 8

Notes

• Your answer should always be a single digit.
• Be sure that it works with very large strings of digits, such as with n>10^20, k>1 000 000 000.

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

Please submit your solutions as comments on this gist.

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

I am surprised that we can just calculate superdigit of n * k

(defn superdigit
  ([n k]
   (superdigit (* n k)))
  ([n]
   (if (<= 10 n)
     (recur (+ (quot n 10) (mod n 10)))
     n)))

(defn superdigit [n k]
  (let [count-digits (fn [p] (loop [p p]
                               (let [res (reduce + (map #(Integer/parseInt (str %)) (str p)))]
                                 (if (< res 10)
                                   res
                                   (recur res)))))
        sp           (count-digits k)
        sp-tot       (* n sp)]
    (count-digits sp-tot)))

(defn digits [n]
  (->> [(rem n 10) (quot n 10)] 
       (iterate (fn [[r q]]
                  [(rem q 10)(quot q 10)]))
       (into () 
             (comp 
              (take-while (fn [[r q]] (some pos? [r q])))
              (map first)
              (map int)))))

(defn unroll [n k]
  (let [digs (digits n)]
    (->> digs (apply +) (* k))))

(defn fold [n]
  (if (< n 10)
    n
    (recur (->> n digits (apply +)))))

(defn superdigit [n k]
  (if (< n 10)
    n
    (fold (unroll n k))))
;;             n k 
(superdigit 1 1) ;=> 1 
(superdigit 10 2) ;=> 2
(superdigit 11 3) ;=> 6 
(superdigit 38 7) ;=> 5
(superdigit 38789789374294723947328946 1000000000000000) ;=> 8
(superdigit (bigint 1.09384e74) 1e15) ;=> 7

(defn digits-sum
  [num]
  (reduce + (map #(Character/digit % 10) (str num))))

(defn superdigit
  [n k]
  (let [p (* k (digits-sum n))]
    (if (= 1 (count (str p)))
      p
      (recur p 1))))

(ns superdigit)

(require '[clojure.string :as str])

(defn superdigit [n k]
  (let [p-cad (->> k
                   (repeat n)
                   (apply str))]
    (loop [cad p-cad]
      (if (= (count cad) 1)
        (Integer/parseInt cad)
        (->> (str/split cad #"")
             (map (fn [elt] (Integer/parseInt elt)))
             (reduce +)
             (str)
             (recur))))))

; Tests
(require '[clojure.test :as test])
(test/testing "superdigit tests"
  (test/is (= (superdigit 12 2) 6))
  (test/is (= (superdigit 1  1) 1))
  (test/is (= (superdigit 10 2) 2))
  (test/is (= (superdigit 11 3) 6))
  (test/is (= (superdigit 38 7) 5)))

(defn digits [n]
  (lazy-seq
   (cons (rem n 10)
         (when (> n 9) (digits (quot n 10))))))

(defn sum-digits [n]
  (apply + (digits n)))

(defn superdigit
  ([n k] (superdigit (* k (sum-digits n))))
  ([p] (let [s (sum-digits p)]
         (if (> s 9)
           (recur s)
           (int s)))))

(defn single-digit?
  [n]
  (= (quot n 10) 0))
​
(defn split-sum
  ([n] (split-sum n 0))
  ([n p-sum]
   (if (single-digit? n)
     (+ n p-sum)
     (recur (rem n 10)
                (+ p-sum (quot n 10))))))
​
(defn superdigit
  [n k]
  (if (single-digit? n)
    (int n)
    (let [p-sum (* (split-sum n) k)]
      (recur p-sum 1))))

(defn sum [nums]
  (->> (partition-all 1 (str nums))
       (reduce #(+ %1 (parse-long (str (first %2)))) 0)))

(defn superdigit [n k]
  (loop [nums (sum n)
           multiplied? false]
      (let [one-digit? (< nums 10)]
        (if (and one-digit? multiplied?)
          nums
          (recur (if one-digit? (* nums k) (sum nums))
                 (if multiplied? true one-digit?))))))