Hitta summan av siffror i ett tal tills summan blir ensiffrig
Givet ett heltal n måste vi upprepade gånger hitta summan av dess siffror tills resultatet blir ett ensiffrigt tal.
Exempel:
Input: n = 1234
Produktion: 1
Förklaring:
Steg 1: 1 + 2 + 3 + 4 = 10
Steg 2: 1 + 0 = 1Input: n = 5674
Produktion: 4
Förklaring:
Steg 1: 5 + 6 + 7 + 4 = 22
Steg 2: 2 + 2 = 4
Innehållsförteckning
- [Naiv metod] Genom att upprepade gånger lägga till siffror
- [Förväntat tillvägagångssätt] Använda matematisk formel
[Naiv metod] Genom att upprepade gånger lägga till siffror
Tillvägagångssättet är inriktat på att beräkna det digitala rummet t av ett tal som är resultatet av att summera siffrorna upprepade gånger tills ett ensiffrigt värde erhålls. Så här fungerar det konceptuellt:
- Summera siffrorna : Börja med att lägga till alla siffror i det angivna numret.
- Kontrollera resultatet : Om summan är ett ensiffrigt tal (dvs mindre än 10) stoppa och returnera den.
- Upprepa processen : Om summan fortfarande är mer än en siffra, upprepa processen med summan av siffror. Detta fortsätter tills en ensiffrig summa uppnås.
// 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
Tidskomplexitet: O(log 10 n) när vi itererar över siffrorna i numret.
Hjälputrymme: O(1)
[Förväntat tillvägagångssätt] Använda matematisk formel
Vi vet att varje tal i decimalsystemet kan uttryckas som summan av dess siffror multiplicerat med 10 potenser. Till exempel ett tal representerat som abcd kan skrivas så här:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Vi kan separera siffrorna och skriva om detta som:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Detta innebär att vilket tal som helst kan uttryckas som summan av dess siffror plus en multipel av 9.
Så om vi tar modulo med 9 på varje sida
abcd % 9 = (a + b + c + d) % 9 + 0Det betyder att resten när abcd divideras med 9 är lika med resten där summan av dess siffror (a + b + c + d) divideras med 9.
Om summan av siffrorna i sig består av mer än en siffra kan vi ytterligare uttrycka denna summa som summan av dess siffror plus en multipel av 9. Följaktligen kommer modulo 9 att eliminera multipeln av 9 tills summan av siffror blir ensiffrigt tal.
Som ett resultat blir summan av siffrorna för ett tal lika med dess modulo 9. Om resultatet av modulooperationen är noll indikerar det att det ensiffriga resultatet är 9.
För att veta om kodimplementering Se Digital rot (upprepad digital summa) av det givna stora heltal
