Recursive Digit Sum

출처 : 해커 랭크

난이도 : 중간

알고리즘 : 재귀

 

 

우리는 정수의 상위 자릿수를 정의합니다.다음 규칙을 사용합니다.

정수가 주어졌을 때, 그 정수의 가장 큰 자리수를 찾아야 합니다 .

• 만약에 x만 가지고있다 1숫자이면 그 슈퍼 숫자는 x.
• 그렇지 않으면, 슈퍼 디지트 x는 각 자리수의 합의 상위 자리수와 같습니다. x.

예를 들어, 슈퍼 디지트 9875다음과 같이 계산됩니다.

	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

숫자 p문자열을 연결하여 생성됩니다 n,k 그래서 초기 p = 9875987598759875.

    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 )  =  슈퍼디지트 ( 8 )

모든 숫자 p합계하다 116. 의 숫자 116합계하다 8. 8숫자가 하나뿐이므로 슈퍼 숫자입니다.

기능 설명

아래 편집기에서 superDigit 함수를 완성하세요 . 계산된 superdigit을 정수로 반환해야 합니다.

superDigit에는 다음과 같은 매개변수가 있습니다.

• 문자열 n: 정수의 문자열 표현
• int k: 연결할 시간n 만들다p

보고

• int: 의 슈퍼 n숫자 k반복타임스

입력 형식

첫 번째 줄에는 공백으로 구분된 두 개의 정수가 포함됩니다.그리고.

제약 조건

• 1 ≤ n ≤10^1000000
• 1 ≤ k ≤10^5

샘플 입력 0

148 3

샘플 출력 0

3

설명 0

여기 n = 148 그리고 k = 3, 그래서 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

샘플 입력 1

9875 4

샘플 출력 1

8

샘플 입력 2

123 3

샘플 출력 2

9

설명 2

여기 n = 123 그리고 k = 3, 그래서 p = 123123123.

super_digit(P) = super_digit(123123123) 
               = super_digit(1+2+3+1+2+3+1+2+3)
               = super_digit(18)
               = super_digit(1+8)
               = super_digit(9)
               = 9

 

----------------------------------------------------------------------------------------------------------------------------

 

문제 해독

주어진 문자열 숫자를 k만큼 반복해서 초기 문자열을 늘리고 각 자리수를 1의 자릿수로 덧셈을 하여 10보다 작은 수가 나올때의 값을 반환하는 문제

 

문제접근

초기값 세팅은 n의 각 자릿수를 더한 값 * k 로 계산 예) n = 123, 1+2+3 = 6, k = 3, 6*3 = 18(설명 2부분과 동일한 값확인)

각 자릿수를 더한 값이 10보다 작을때까지 재귀

 

public static int superDigit(string n, int k)
    {
        long digitSum = 0;
        foreach(char c in n)
        {
            digitSum += (c - '0');
        }
    
        long totalSum = digitSum * k;
    
        return super_digit_helper(totalSum);
    }

    private static int super_digit_helper(long number)
    {
        if(number < 10)
            return (int)number;
    
        long sum = 0;
        while(number > 0)
        {
            sum += number % 10;
            number /= 10;
        }
    
        return super_digit_helper(sum);
    }
    
    private static int[] GetSplitNumbers(int number)
    {
        int length = number.ToString().Length;
        int[] newNumbers = new int[length];
        
        for(int i = 0; i < length; i++)
        {
            newNumbers[i] = number % 10;
            number /= 10;
        }
        return newNumbers;
    }