Iskanje vsote števk števila, dokler vsota ne postane enomestna
Za dano celo število n moramo večkrat poiskati vsoto njegovih števk, dokler rezultat ne postane enomestno število.
Primeri:
Vnos: n = 1234
Izhod: 1
Pojasnilo:
1. korak: 1 + 2 + 3 + 4 = 10
2. korak: 1 + 0 = 1Vnos: n = 5674
Izhod: 4
Pojasnilo:
1. korak: 5 + 6 + 7 + 4 = 22
2. korak: 2 + 2 = 4
Kazalo vsebine
[Naivni pristop] S ponavljajočim seštevanjem števk
Pristop je osredotočen na izračun digitalne roo t števila, ki je rezultat ponavljajočega seštevanja števk, dokler ne dobimo enomestne vrednosti. Evo, kako konceptualno deluje:
- Seštejte števke : Začnite tako, da seštejete vse števke dane številke.
- Preverite rezultat : Če je vsota enomestno število (tj. manj kot 10), se ustavite in vrnite.
- Ponovite postopek : Če je vsota še vedno večja od ene števke, ponovite postopek z vsoto števk. To se nadaljuje, dokler ni dosežena enomestna vsota.
// 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 ));
Izhod
1
Časovna zapletenost: O(log 10 n), ko ponavljamo števke števila.
Pomožni prostor: O(1)
[Pričakovan pristop] Uporaba matematične formule
Vemo, da je vsako število v decimalnem sistemu mogoče izraziti kot vsoto svojih števk, pomnoženih s potencami števila 10. Na primer, število, predstavljeno kot abcd lahko zapišemo takole:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Številke lahko ločimo in to prepišemo kot:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
To pomeni, da je katero koli število mogoče izraziti kot vsoto svojih števk plus večkratnik števila 9.
Torej, če vzamemo modulo z 9 na vsaki strani
abcd % 9 = (a + b + c + d) % 9 + 0To pomeni, da je ostanek, ko je abcd deljen z 9, enak ostanku, kjer je vsota njegovih števk (a + b + c + d) deljena z 9.
Če je sama vsota števk sestavljena iz več kot ene števke, lahko to vsoto nadalje izrazimo kot vsoto njenih števk plus večkratnik števila 9. Posledično bo uporaba modula 9 odpravila večkratnik števila 9, dokler vsota števk ne postane enomestno število.
Posledično bo vsota števk katerega koli števila enaka njegovemu modulu 9. Če je rezultat operacije modulo nič, pomeni, da je enomestni rezultat 9.
Če želite vedeti o implementaciji kode, Glejte Digitalni koren (ponavljajoča se digitalna vsota) danega velikega celega števila
