Egy szám számjegyeinek összegének megkeresése, amíg az összeg egyjegyűvé nem válik
Adott n egész szám ismételten meg kell találnunk a számjegyeinek összegét, amíg az eredmény egyjegyű szám nem lesz.
Példák:
Bemenet: n = 1234
Kimenet: 1
Magyarázat:
1. lépés: 1 + 2 + 3 + 4 = 10
2. lépés: 1 + 0 = 1Bemenet: n = 5674
Kimenet: 4
Magyarázat:
1. lépés: 5 + 6 + 7 + 4 = 22
2. lépés: 2 + 2 = 4
Tartalomjegyzék
- [Naiv megközelítés] Számjegyek ismétlődő hozzáadásával
- [Elvárt megközelítés] Matematikai képlet használata
[Naiv megközelítés] Számjegyek ismétlődő hozzáadásával
A megközelítés a digitális roo kiszámítására összpontosít t egy szám, amely a számjegyek ismételt összegzésének eredménye, amíg egyjegyű értéket nem kapunk. Elvileg a következőképpen működik:
- Adja össze a számjegyeket : Kezdje a megadott szám összes számjegyének összeadásával.
- Ellenőrizze az eredményt : Ha az összeg egyjegyű szám (azaz 10-nél kisebb), állítsa le, és adja vissza.
- Ismételje meg a folyamatot : Ha az összeg még mindig több egy számjegynél, ismételje meg a folyamatot a számjegyek összegével. Ez addig folytatódik, amíg el nem ér egy egyjegyű összeget.
// 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 ));
Kimenet
1
Időbeli összetettség: O(log 10 n) ahogy iteráljuk a szám számjegyeit.
Kiegészítő tér: O(1)
[Elvárt megközelítés] Matematikai képlet használata
Tudjuk, hogy a decimális rendszerben minden szám kifejezhető úgy, hogy a számjegyei összege szorozzuk 10 hatványaival. abcd a következőképpen írható:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
A számjegyeket szétválaszthatjuk és átírhatjuk a következőképpen:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Ez azt jelenti, hogy tetszőleges szám kifejezhető a számjegyeinek és a 9 többszörösének összegével.
Tehát ha úgy vesszük a modulot, hogy mindkét oldalon 9
abcd % 9 = (a + b + c + d) % 9 + 0Ez azt jelenti, hogy az abcd 9-cel való osztásakor a maradék egyenlő azzal a maradékkal, ahol a számjegyeinek összegét (a + b + c + d) elosztjuk 9-cel.
Ha maga a számjegyek összege egynél több számjegyből áll, akkor ezt az összeget a számjegyeinek összegeként plusz 9 többszöröseként is kifejezhetjük. Következésképpen a modulo 9 figyelembevételével a 9 többszöröse megszűnik, amíg a számjegyek összege egyjegyű számmá nem válik.
Ennek eredményeként bármely szám számjegyeinek összege a modulo 9 lesz. Ha a modulo művelet eredménye nulla, az azt jelzi, hogy az egyjegyű eredmény 9.
A kód implementációjáról lásd Az adott nagy egész szám Digital Root (ismételt digitális összege).
