합이 한 자리가 될 때까지 숫자의 자릿수 합 구하기
정수 n이 주어지면 결과가 한 자리 숫자가 될 때까지 숫자의 합을 반복적으로 찾아야 합니다.
예:
입력: n = 1234
산출: 1
설명:
1단계: 1 + 2 + 3 + 4 = 10
2단계: 1 + 0 = 1입력: n = 5674
산출: 4
설명:
1단계: 5 + 6 + 7 + 4 = 22
2단계: 2 + 2 = 4
목차
[순진한 접근 방식] 반복적으로 숫자를 추가하여
접근 방식은 디지털 루 계산에 중점을 둡니다. 티 한 자리 값을 얻을 때까지 숫자를 반복적으로 합산한 결과인 숫자입니다. 개념적으로 작동하는 방법은 다음과 같습니다.
- 숫자를 합산하세요 : 주어진 숫자의 모든 숫자를 더하는 것부터 시작하세요.
- 결과 확인 : 합계가 한 자리 숫자(예: 10 미만)인 경우 중지하고 반환합니다.
- 과정을 반복하세요 : 합계가 여전히 한 자리보다 크면 자릿수 합계로 프로세스를 반복합니다. 이는 한 자릿수 합계에 도달할 때까지 계속됩니다.
// C++ program to find the digit sum by // repetitively Adding its digits #include using namespace std ; int singleDigit ( int n ) { int sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n == 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n /= 10 ; } return sum ; } int main () { int n = 1234 ; cout < < singleDigit ( n ); return 0 ; }
C // C program to find the digit sum by // repetitively Adding its digits #include int singleDigit ( int n ) { int sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n == 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n /= 10 ; } return sum ; } int main () { int n = 1234 ; printf ( '%d' singleDigit ( n )); return 0 ; }
Java // Java program to find the digit sum by // repetitively Adding its digits class GfG { static int singleDigit ( int n ) { int sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n == 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n /= 10 ; } return sum ; } public static void main ( String [] args ) { int n = 1234 ; System . out . println ( singleDigit ( n )); } }
Python # Python program to find the digit sum by # repetitively Adding its digits def singleDigit ( n ): sum = 0 # Repetitively calculate sum until # it becomes single digit while n > 0 or sum > 9 : # If n becomes 0 reset it to sum # and start a new iteration if n == 0 : n = sum sum = 0 sum += n % 10 n //= 10 return sum if __name__ == '__main__' : n = 1234 print ( singleDigit ( n ))
C# // C# program to find the digit sum by // repetitively Adding its digits using System ; class GfG { static int singleDigit ( int n ) { int sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n == 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n /= 10 ; } return sum ; } static void Main () { int n = 1234 ; Console . WriteLine ( singleDigit ( n )); } }
JavaScript // JavaScript program to find the digit sum by // repetitively Adding its digits function singleDigit ( n ) { let sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n === 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n = Math . floor ( n / 10 ); } return sum ; } // Driver Code const n = 1234 ; console . log ( singleDigit ( n ));
산출
1
시간 복잡도: 오(로그 10 n) 숫자의 숫자를 반복하는 중입니다.
보조 공간: 오(1)
[예상 접근 방식] 수학 공식을 활용
우리는 십진법의 모든 숫자가 그 숫자의 합에 10의 거듭제곱을 곱한 값으로 표현될 수 있다는 것을 알고 있습니다. 예를 들어 다음과 같이 표현되는 숫자는 다음과 같습니다. ABCD 다음과 같이 쓸 수 있습니다:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
숫자를 분리하여 다음과 같이 다시 쓸 수 있습니다.
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
이는 모든 숫자가 해당 숫자의 합과 9의 배수로 표현될 수 있음을 의미합니다.
따라서 각 변에 9를 모듈로 취하면
abcd % 9 = (a + b + c + d) % 9 + 0이는 abcd를 9로 나눈 나머지가 해당 자릿수(a + b + c + d)의 합을 9로 나눈 나머지와 같다는 의미입니다.
숫자의 합 자체가 둘 이상의 숫자로 구성된 경우 이 합을 해당 숫자의 합에 9의 배수를 더한 값으로 더 표현할 수 있습니다. 결과적으로 모듈로 9를 사용하면 숫자의 합이 한 자리 숫자가 될 때까지 9의 배수가 제거됩니다.
결과적으로 모든 숫자의 자릿수 합계는 모듈로 9와 같습니다. 모듈로 연산의 결과가 0이면 한 자리 숫자 결과가 9임을 나타냅니다.
코드 구현에 대해 알고 싶다면 참조하세요 주어진 큰 정수의 디지털 루트(반복된 디지털 합계)
