HackerRank : Recursive Digit Sum

문제 링크

HackerRank : Recursive Digit Sum (Click)

문제 요약

1. 1 <= n < 10^100000 와 1 <= k <= 10^5가 주어진다.

2. superDigit이라는 메서드는 다음과 같이 동작해야 한다.

   // n = 9875, k = 1
   
    super_digit(9875)       9+8+7+5 = 29 
    super_digit(29)     2 + 9 = 11
    super_digit(11)        1 + 1 = 2
    super_digit(2)        = 2  

   // n = 9875, k = 4
    superDigit(p) = superDigit(9875987598759875)
                  9+8+7+5+9+8+7+5+9+8+7+5+9+8+7+5 = 116
    superDigit(p) = superDigit(116)
                  1+1+6 = 8
    superDigit(p) = superDigit(8)

3. superDigit을 구현하라.

문제 풀이

    public static int superDigit(String n, int k) {
    // Write your code here
        long sum = 0;
        for(int i=0; i<n.length(); i++) {
            sum += Integer.valueOf(n.charAt(i)-48);
        }
        sum *= k;
        return calculator(sum);
    }

    public static int calculator(long n) {
        if(n<10) return (int)n;
        long sum = 0;
        while(n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return calculator(sum);
    }
}

비슷한 재귀 로직으로 접근했으나, 처음에는 Time Out이 발생했다.
조건 1 <= n < 10^100000 와 1 <= k <= 10^5를 간과해서 발생했다.

시간 복잡도

O(log(k))