[HackerRank - Java] Day 4 - 2. Recursive Digit Sum

2023. 1. 28. 23:42Java/coding test

반응형

Recursive Digit Sum

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

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

  • If has only 11 digit, then its super digit is xx.
  • Otherwise, the super digit of xx is equal to the super digit of the sum of the digits of xx.

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=9875n = '9875'
k=4k = 4

The number pp is created by concatenating the string nn kk times so the initial p=9875987598759875p = 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 pp sum to 116116. The digits of 116116 sum to 88. 88 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 to make

Returns

  • int: the super digit of repeated times

Input Format

The first line contains two space separated integers, and .

Constraints

  • 1<=n<101000001 <= n < 10^{100000}
  • 1<=k<=1051 <= k <= 10^5

숫자로 이뤄진 문자열 n
각 자리수의 합을 구하는 것을 super digit 이라고 할 때,

k 수만큼 n을 반복하고,
문자열의 각 자리 수를 한자리수가 될 때까지 합산하는 코드를 짜면 됩니다.


n이 '124'고 k가 3이라 하면,
'124124124' 의 super digit을 구하면 되는 건데

이는 '124'의 super digit을 3번 곱한 것과 같다.

1+2+4+1+2+4+1+2+4=(1+2+4)31 + 2 + 4 + 1 + 2 + 4 + 1 + 2 + 4 = (1 + 2 + 4) * 3

이떄, 문자열 n이 1010000010^{100000} 길이만큼 가능하기 때문에 int나 long으로 parse하면 표현 범위가 초과하여 오류가 나기 때문에, String을 char로 쪼개서 합산하는 방식을 사용하는 것이 좋습니다.


static int superDigit(String n, int k) {
		long result = sum(n) * k;
		while (result > 10) {
				result = sum(String.valueOf(result));
		}

		return (int)result;
}

static long sum(String n) {
		if(n.length() == 1) return Long.parseLong(n);
		long result = 0;
		for (char ch : n.toCharArray()) {
				result += Character.getNumericValue(ch);
		}
		return result;
}
728x90
반응형