[HackerRank] Recursive Digit Sum

Problem

---

We define super digit of an integer x using the following rules:

Given an integer, we need to find the super digit of the integer.

• If 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 sum of the digits of x.

For example, the super digit of 9875 will be calculated as:

	super_digit(9875)   	9+8+7+5 = 29 
	super_digit(29) 	2 + 9 = 11
	super_digit(11)		1 + 1 = 2
	super_digit(2)		= 2

 

Example
n = ' 9875'

k = 4

The number p is created by concatenating the string n k times so the initial 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) = superDigit(8)

All of the digits of p sum to 116. The digits of 116 sum to 8. 8 is only one digit, so it is the super digit.

 

Function Description

Complete the function superDigit in the editor below. It must return the calculated super digit as an integer.

superDigit has the following parameter(s):

• string n: a string representation of an integer
• int k: the times to concatenate n to make p

Returns

• int: the super digit of n repeated k times

Input Format

The first line contains two space separated integers, n and k.

Constraints

1 ≤ n ≤ 10^100000

1 ≤ k ≤ 10^5

---

슈퍼 디지트(super digit)를 다음 규칙에 따라 정의합니다:

1. 주어진 정수 xxx가 한 자리 숫자라면, 그 숫자가 바로 슈퍼 디지트입니다.
2. xxx가 한 자리 숫자가 아니라면, xxx의 각 자리 숫자의 합으로 슈퍼 디지트를 구합니다.
   이를 반복하여 최종적으로 한 자리 숫자가 될 때까지 진행합니다.

예를 들어, 9875의 슈퍼 디지트를 구하는 과정은 다음과 같습니다:

• super_digit(9875): 9+8+7+5=299 + 8 + 7 + 5 = 299+8+7+5=29
• super_digit(29): 2+9=112 + 9 = 112+9=11
• super_digit(11): 1+1=21 + 1 = 21+1=2
• super_digit(2): 한 자리 숫자이므로 최종 슈퍼 디지트는 2입니다.

예제

• n=9875n = 9875n=9875
• k=4k = 4k=4

문자열 nnn을 kkk번 반복하여 p=9875987598759875p = 9875987598759875p=9875987598759875를 생성합니다.

• super_digit(p) = super_digit(9875987598759875)
  9+8+7+5+9+8+7+5+9+8+7+5+9+8+7+5=1169 + 8 + 7 + 5 + 9 + 8 + 7 + 5 + 9 + 8 + 7 + 5 + 9 + 8 + 7 + 5 = 1169+8+7+5+9+8+7+5+9+8+7+5+9+8+7+5=116
• super_digit(116): 1+1+6=81 + 1 + 6 = 81+1+6=8
• super_digit(8): 한 자리 숫자이므로 최종 슈퍼 디지트는 8입니다.

 

 

Solution

---

public static int superDigit(String n, int k) {
    // n의 모든 자리 숫자의 합을 구합니다
    long sum = 0;
    for (char digit : n.toCharArray()) {
        sum += Character.getNumericValue(digit);
    }
    
    // 이 합을 k배하여 초기 슈퍼 디지트를 계산합니다
    long initialSuperDigit = sum * k;
    
    // 한 자리 숫자가 나올 때까지 슈퍼 디지트를 재귀적으로 구합니다
    return calculateSuperDigit(initialSuperDigit);
}

// 재귀적으로 슈퍼 디지트를 계산하는 헬퍼 함수
private static int calculateSuperDigit(long num) {
    if (num < 10) {
        return (int) num;
    }
    
    long sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    
    return calculateSuperDigit(sum);
}

 

 

• 자리 숫자의 합 구하기
  • n.toCharArray()를 사용하여 nnn의 각 자리 숫자를 char로 변환합니다.
    • 이 구문은 문자열 nnn의 각 문자를 한 번에 하나씩 꺼내어 반복할 때 사용됩니다.
    • n.toCharArray()는 문자열을 문자 배열(char array)로 변환하는 메서드로, 문자열을 개별 문자 단위로 분리해 처리할 수 있게 합니다.
      • for 루프가 n.toCharArray()의 각 문자를 digit 변수에 할당합니다.
      • digit은 하나의 문자(char)를 나타내므로 9, 8, 7 등 하나의 자리 숫자 문자가 됩니다.
      이 반복문을 통해 문자열 nnn의 모든 자리 숫자를 하나씩 처리할 수 있습니다.
  • Character.getNumericValue(digit)는 문자(char) 형식으로 표현된 숫자를 정수(int) 형식으로 변환합니다.
    • 예를 들어, digit이 문자 '9'인 경우, Character.getNumericValue('9')는 정수 9를 반환합니다.
    • 이 메서드를 통해 문자열 n의 각 자리 숫자를 실제 숫자값으로 변환하여 합을 구할 수 있습니다.
• 초기 슈퍼 디지트 계산
  • 자리 숫자의 합에 kkk를 곱하여 nnn이 kkk번 반복된 전체 수의 자리 합을 구합니다.
• 재귀적 계산
  • calculateSuperDigit() 헬퍼 함수는 한 자리 숫자가 나올 때까지 재귀적으로 자리 합을 반복합니다.
  • 이 함수 호출은 최종 슈퍼 디지트를 재귀적으로 계산하는 단계입니다. initialSuperDigit은 nnn의 자리 숫자 합에 kkk를 곱한 값입니다.calculateSuperDigit 함수의 작동 방식:
    • 첫 번째 조건문에서 숫자가 한 자리 숫자(num < 10)일 경우, 해당 숫자를 반환합니다. 즉, 슈퍼 디지트 계산이 종료되는 조건입니다.
    • 그렇지 않다면, num의 자리 숫자를 분해하고 모두 더하여 새로운 sum을 구합니다.
    • 이 sum을 다시 calculateSuperDigit에 전달하여 슈퍼 디지트가 나올 때까지 과정을 반복합니다.
  • calculateSuperDigit 함수는 한 자리 숫자가 나올 때까지 반복해서 자리 숫자들의 합을 구합니다.

이 방식으로 최종적으로 한 자리 슈퍼 디지트가 도출될 때까지 자리 합을 구하는 작업이 반복됩니다.