# Super Digit

# Super Digit

imvladikon + 0 comments another way of solution - mod 9

Rhaseven7h + 1 comment ### Memory Errors? Timeouts?

Usually that means your algorithm is flawed. When you get timeouts, it means you have to optimize speed. When you get out-of-memories, it measn you have to optimize for space.

### Hint! Spoiler!

In this case, realize that the sum of digits of

`"big number of digits here" + ... + "big number of digits here"`

with the above concatenation/replication`N`

times, and getting the`sum`

of the huge, gigantic number, is equal to the sum of the digits`"big number of digits here"`

times`N`

.i.e. with

`n=12345`

and`k=5`

:# "12345" replicated 5 times = "1234512345123451234512345", if you get one of the test cases with a string 1,000 characters long, replicated 10,000 times, you end up with a number of 100,000 digits. Non-sense. sumOfDigits("1234512345123451234512345") = 75 # is exactly the same as 5 * sumOfDigits("12345") = 15 5 * 15 = 75 # From here on, all digit-sums are quick and ease

### SOLUTION (SPOILER) IN HASKELL

Full solution here (

): Rhaseven7h's Gists*FULL SPOILER*Hope this helps some one.

satyajitghana191 + 0 comments [deleted]

hibernicus + 0 comments Wonderful challenge, one of the most entertaining ones I've done. Although the experience was slightly spoiled by reading some of the comments here (basically giving the entire solution away), it may be that I should be thanking them since I didn't want to stop and go to sleep before I finished this :) The testcase 9 was rather tricky though and I ended up leaving a rather nasty looking hack for it, maybe I'll fix it after a good night's sleep.

naderghanbari + 0 comments We're asked to solve this with recursion as a practice, but there's a faster way using the fact that powers of ten are all

`1`

modulo`9`

. One can also filter out all`0`

's and`9`

's from both numbers before multiplying the sum of their digits.val nk = readLine().split(" ").map(_.map(_.asDigit).sum).map(_%9).product val magic = if (nk%9 == 0) 9 else nk%9

ddfhznq01 + 0 comments java solution o(1) public static int superDigit(String n, int k) {

`if (n == null) return 0; if (k == 0) { return suberDigit(data); } long data = Long.valueOf(n); int i = suberDigit(data); int res = i * k; if (res <= 9) { return res; } return suberDigit(res); } static int suberDigit(long data) { if (data == 0) { return 0; } if (data % 9 == 0) { return 9; } else { return (int) (data % 9); } }`

Benjamin_A_Luna + 0 comments My

**F#**solution.let SplitDigits (s: string) = s |> Seq.map(fun x -> (x |> int64) - (48 |> int64)) |> Seq.toList let main = let rec SumDigits digit : int64 = match digit with | head :: tail -> head + SumDigits tail | [] -> 0 |> int64 let rec GetSuper (number: int64 list) : int64 = let Super = SumDigits number if Super > (9 |> int64) then GetSuper (SplitDigits (Super |> string)) else Super let nk = Console.ReadLine().Split(" ") let digits = (((SplitDigits nk.[0] |> SumDigits) * (nk.[1] |> int64) ) |> string |> SplitDigits) GetSuper digits |> Console.WriteLine

satyajitghana191 + 1 comment digSum :: Integer -> Integer digSum x | x < 9 = x | otherwise = digSum $ x `mod` 10 + x `div` 10 findSum :: [Integer] -> Integer findSum n = digSum $ y * digSum x where x = head n y = head $ tail n solve = findSum . map read . words main = interact $ show . solve

why would this not work for test case 9 ?

Wielomian + 1 comment In function digSum you probably wanted a case "x < 10", since with x = 9 you just enter infinite loop.

satyajitghana191 + 0 comments yeah you are right, should have been x < 10

dmitrykosykh + 0 comments Here is a solution on Racket, you only need to optimize for the last two tests.

#lang racket (define (number->list number) (if (< number 10) (cons number null) (cons (modulo number 10) (number->list (floor (/ number 10)))))) (define (super-digit number) (if (< number 10) number (super-digit (foldl + 0 (number->list number))))) (let ([number (read)] [i [read]]) (super-digit (foldl + 0 (make-list i (super-digit number)))))

gschoen + 0 comments Although Lisp can handle numbers as big as 10^100000 the program will time out for the big test cases. I suspect that division is implemented as a repeated shift and subtract operation so that repeatedly dividing 10^n by 10 (to get the individual digits) will run in O(n^2) time.

The solution is to read the first number as a character string and process each character one at a time.(defun sumstring (s n r) (if (< n 0) r (sumstring s (1- n) (+ (parse-integer (string (aref s n))) r)))) (defun sumdigits (n p) (if (zerop n) p (sumdigits (floor (/ n 10)) (+ (rem n 10) p)))) (defun superdigit (x) (let ((n (sumdigits x 0))) (if (< n 10) n (superdigit n)))) (let ((str (write-to-string (read))) (k (read))) (format t "~A~%" (superdigit (* (sumstring str (1- (length str)) 0) k))))

yarel79 + 0 comments In Scala:

def superDigit(n : String, k : Long): Long = n.length match { case 1 if k==1 => n.toLong case _ => superDigit((n.chars().filter(_ != 48).map(_-48).asLongStream().sum()*k).toString, 1) }

Sort 27 Discussions, By:

Please Login in order to post a comment