Find summen af cifre i et tal, indtil sum bliver enkeltcifret
Givet et heltal n skal vi gentagne gange finde summen af dets cifre, indtil resultatet bliver et enkeltcifret tal.
Eksempler:
Input: n = 1234
Produktion: 1
Forklaring:
Trin 1: 1 + 2 + 3 + 4 = 10
Trin 2: 1 + 0 = 1Input: n = 5674
Produktion: 4
Forklaring:
Trin 1: 5 + 6 + 7 + 4 = 22
Trin 2: 2 + 2 = 4
Indholdsfortegnelse
[Naiv tilgang] Ved gentagne gange at tilføje cifre
Tilgangen er fokuseret på at beregne det digitale rum t af et tal, som er resultatet af summering af cifrene gentagne gange, indtil der opnås en enkeltcifret værdi. Sådan fungerer det konceptuelt:
- Sum cifrene : Start med at tilføje alle cifrene i det givne nummer.
- Tjek resultatet : Hvis summen er et enkeltcifret tal (dvs. mindre end 10), stop og returner det.
- Gentag processen : Hvis summen stadig er mere end et enkelt ciffer, gentag processen med summen af cifre. Dette fortsætter, indtil en enkeltcifret sum er nået.
// 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 ));
Produktion
1
Tidskompleksitet: O(log 10 n) mens vi itererer over cifrene i nummeret.
Hjælpeplads: O(1)
[Forventet tilgang] Brug af matematisk formel
Vi ved, at hvert tal i decimalsystemet kan udtrykkes som summen af dets cifre ganget med 10 potenser. For eksempel et tal repræsenteret som abcd kan skrives som følger:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Vi kan adskille cifrene og omskrive dette som:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Dette indebærer, at ethvert tal kan udtrykkes som summen af dets cifre plus et multiplum af 9.
Så hvis vi tager modulo med 9 på hver side
abcd % 9 = (a + b + c + d) % 9 + 0Det betyder, at resten, når abcd divideres med 9, er lig med resten, hvor summen af dens cifre (a + b + c + d) er divideret med 9.
Hvis summen af cifrene i sig selv består af mere end et ciffer, kan vi yderligere udtrykke denne sum som summen af dets cifre plus et multiplum af 9. Følgelig vil modulo 9 eliminere multiplum af 9, indtil summen af cifre bliver til et-cifret tal.
Som et resultat vil summen af cifrene af ethvert tal lig med dets modulo 9. Hvis resultatet af modulo-operationen er nul, indikerer det, at det encifrede resultat er 9.
For at vide om kodeimplementering Se Digital rod (gentaget digital sum) af det givne store heltal
