階：更好的解決方案

Question

問題：
我們定義一個整數的超級數字乘以使用下列規則：

Iff x has only 1 digit, then its super digit is x. 
Otherwise, the super digit of x is equal to the super digit of the digit-sum of x. Here, digit-sum of a number is defined as the sum of its digits. 
For example, super digit of 9875 will be calculated as: 

super-digit(9875) = super-digit(9+8+7+5) 
        = super-digit(29) 
        = super-digit(2+9) 
        = super-digit(11) 
        = super-digit(1+1) 
        = super-digit(2) 
        = 2. 
You are given two numbers - n k. You have to calculate the super digit of P. 

P is created when number n is concatenated k times. That is, if n = 123 and k = 3, then P = 123123123. 

Input Format 
Input will contain two space separated integers, n and k. 

Output Format 

Output the super digit of P, where P is created as described above. 

Constraint 

1≤n<10100000 
1≤k≤105 
Sample Input 

148 3 
Sample Output 

3 
Explanation 
Here n = 148 and k = 3, so P = 148148148. 

super-digit(P) = super-digit(148148148) 
       = super-digit(1+4+8+1+4+8+1+4+8) 
       = super-digit(39) 
       = super-digit(3+9) 
       = super-digit(12) 
       = super-digit(1+2) 
       = super-digit(3) 
       = 3. 

我寫了下面的程序，以解決上述問題，但怎麼也能有效地解決這個問題並且是比數學運算更高效的字符串操作？並投入少花費很長的時間，例如

object SuperDigit { 
    def main(args: Array[String]) { 
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution 
*/ 
    def generateString (no:String,re:BigInt , tot:BigInt , temp:String):String = { 
     if(tot-1>re) generateString(no+temp,re+1,tot,temp) 
     else no 
    } 
    def totalSum(no:List[Char]):BigInt = no match { 
     case x::xs => x.asDigit+totalSum(xs) 
     case Nil => '0'.asDigit 


    } 

    def tot(no:List[Char]):BigInt = no match { 
     case _ if no.length == 1=> no.head.asDigit 
     case no => tot(totalSum(no).toString.toList) 

    } 
    var list = readLine.split(" "); 
    var one = list.head.toString(); 
    var two = BigInt(list(1)); 
    //println(generateString("148",0,3,"148")) 
    println(tot(generateString(one,BigInt(0),two,one).toList)) 
    } 

} 

Answer 1

一個減少意識到，你不必來連接視爲一個字符串k次的數量，而是可以與啓動數字k * qs（n）（其中qs是將數字映射到數字總和的函數，即qs（123）= 1 + 2 + 3）。這是一個更具功能性的編程時尚方法。我不知道它是否可以做得比這更快。

object Solution { 

    def qs(n: BigInt): BigInt = n.toString.foldLeft(BigInt(0))((n, ch) => n + (ch - '0').toInt) 

    def main(args: Array[String]) { 
    val input = scala.io.Source.stdin.getLines 

    val Array(n, k) = input.next.split(" ").map(BigInt(_)) 

    println(Stream.iterate(k * qs(n))(qs(_)).find(_ < 10).get) 
    } 
}