Hľadanie súčtu číslic čísla, kým sa súčet nestane jednou číslicou
Dané celé číslo n musíme opakovane nájsť súčet jeho číslic, až kým výsledkom nebude jednociferné číslo.
Príklady:
Vstup: n = 1234
výstup: 1
Vysvetlenie:
Krok 1: 1 + 2 + 3 + 4 = 10
Krok 2: 1 + 0 = 1Vstup: n = 5674
výstup: 4
Vysvetlenie:
Krok 1: 5 + 6 + 7 + 4 = 22
Krok 2: 2 + 2 = 4
Obsah
[Naivný prístup] Opakovaným pridávaním číslic
Prístup je zameraný na výpočet digitálneho priestoru t čísla, ktoré je výsledkom opakovaného sčítania číslic, kým sa nezíska jednociferná hodnota. Koncepčne to funguje takto:
- Spočítajte číslice : Začnite sčítaním všetkých číslic daného čísla.
- Skontrolujte výsledok : Ak je súčet jednociferné číslo (t. j. menej ako 10), zastavte a vráťte ho.
- Opakujte postup : Ak je súčet stále väčší ako jedna číslica, zopakujte postup so súčtom číslic. Toto pokračuje, kým sa nedosiahne jednociferný súč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 ));
Výstup
1
Časová zložitosť: O(log 10 n), pretože iterujeme cez číslice čísla.
Pomocný priestor: O(1)
[Očakávaný prístup] Použitie matematického vzorca
Vieme, že každé číslo v desiatkovej sústave možno vyjadriť ako súčet jeho číslic vynásobený mocninou 10. Napríklad číslo reprezentované ako abcd možno napísať nasledovne:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Môžeme oddeliť číslice a prepísať to takto:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
To znamená, že akékoľvek číslo môže byť vyjadrené ako súčet jeho číslic plus násobok 9.
Ak teda vezmeme modulo s 9 na každej strane
abcd % 9 = (a + b + c + d) % 9 + 0To znamená, že zvyšok pri delení abcd 9 sa rovná zvyšku, kde súčet jeho číslic (a + b + c + d) je delený 9.
Ak samotný súčet číslic pozostáva z viac ako jednej číslice, môžeme tento súčet ďalej vyjadriť ako súčet jeho číslic plus násobok 9. Následne, keď použijeme modulo 9, odstránime násobok 9, kým sa zo súčtu číslic nestane jednociferné číslo.
Výsledkom je, že súčet číslic akéhokoľvek čísla sa bude rovnať jeho modulo 9. Ak je výsledok operácie modulo nula, znamená to, že jednociferný výsledok je 9.
Ak chcete vedieť o implementácii kódu, pozrite si Digitálny koreň (opakovaný digitálny súčet) daného veľkého celého čísla
