Hledání součtu číslic čísla, dokud se součet nestane jednou číslicí
Je-li dané celé číslo n, musíme opakovaně najít součet jeho číslic, dokud se výsledkem nestane jednociferné číslo.
Příklady:
Vstup: n = 1234
výstup: 1
Vysvětlení:
Krok 1: 1 + 2 + 3 + 4 = 10
Krok 2: 1 + 0 = 1Vstup: n = 5674
výstup: 4
Vysvětlení:
Krok 1: 5 + 6 + 7 + 4 = 22
Krok 2: 2 + 2 = 4
Obsah
[Naivní přístup] Opakovaným přidáváním číslic
Přístup je zaměřen na výpočet digitální místnosti t čísla, které je výsledkem opakovaného sčítání číslic, dokud není získána jednociferná hodnota. Zde je návod, jak to koncepčně funguje:
- Sečtěte číslice : Začněte sečtením všech číslic daného čísla.
- Zkontrolujte výsledek : Pokud je součet jednomístné číslo (tj. méně než 10), zastavte a vraťte jej.
- Opakujte postup : Pokud je součet stále více než jedna číslice, opakujte postup se součtem číslic. Toto pokračuje, dokud není dosaženo jednociferného součtu.
// 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á náročnost: O(log 10 n) jak iterujeme přes číslice čísla.
Pomocný prostor: O(1)
[Očekávaný přístup] Použití matematického vzorce
Víme, že každé číslo v desítkové soustavě lze vyjádřit jako součet jeho číslic vynásobený mocninami 10. Například číslo reprezentované jako abcd lze napsat následovně:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Můžeme oddělit číslice a přepsat 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 jakékoli číslo může být vyjádřeno jako součet jeho číslic plus násobek 9.
Pokud tedy vezmeme modulo s 9 na každé straně
abcd % 9 = (a + b + c + d) % 9 + 0To znamená, že zbytek, když je abcd děleno 9, se rovná zbytku, kde součet jeho číslic (a + b + c + d) je dělený 9.
Pokud se samotný součet číslic skládá z více než jedné číslice, můžeme tento součet dále vyjádřit jako součet jeho číslic plus násobek 9. Následně použití modulu 9 odstraní násobek 9, dokud se součet číslic nestane jednociferným číslem.
Výsledkem je, že součet číslic libovolného čísla se bude rovnat jeho modulo 9. Pokud je výsledek operace modulo nula, znamená to, že jednociferný výsledek je 9.
Chcete-li vědět o implementaci kódu, viz Digitální odmocnina (opakovaný digitální součet) daného velkého celého čísla
