Skaičiaus skaitmenų sumos radimas, kol suma tampa vienženkle
Duodami sveikąjį skaičių n, turime pakartotinai rasti jo skaitmenų sumą, kol rezultatas taps vienaženkliu skaičiumi.
Pavyzdžiai:
Įvestis: n = 1234
Išvestis: 1
Paaiškinimas:
1 veiksmas: 1 + 2 + 3 + 4 = 10
2 veiksmas: 1 + 0 = 1Įvestis: n = 5674
Išvestis: 4
Paaiškinimas:
1 veiksmas: 5 + 6 + 7 + 4 = 22
2 veiksmas: 2 + 2 = 4
Turinio lentelė
- [Naivus požiūris] Pakartotinai pridedant skaitmenis
- [Numatomas metodas] Naudojant matematinę formulę
[Naivus požiūris] Pakartotinai pridedant skaitmenis
Šis metodas yra orientuotas į skaitmeninio roo apskaičiavimą t skaičiaus, kuris yra pakartotinai sumuojant skaitmenis, kol gaunama vienaženklė reikšmė. Štai kaip tai veikia konceptualiai:
- Sumuokite skaičius : Pradėkite pridėdami visus nurodyto skaičiaus skaitmenis.
- Patikrinkite rezultatą : Jei suma yra vienaženklis skaičius (ty mažiau nei 10), sustokite ir grąžinkite.
- Pakartokite procesą : Jei suma vis tiek yra daugiau nei vienas skaitmuo, pakartokite procesą su skaitmenų suma. Tai tęsiasi tol, kol pasiekiama vienaženklė suma.
// 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 ));
Išvestis
1
Laiko sudėtingumas: O(log 10 n) kartojame per skaičiaus skaitmenis.
Pagalbinė erdvė: O(1)
[Numatomas metodas] Naudojant matematinę formulę
Žinome, kad kiekvienas skaičius dešimtainėje sistemoje gali būti išreikštas jo skaitmenų suma, padauginta iš laipsnių 10. Pavyzdžiui, skaičius, pavaizduotas kaip abcd galima parašyti taip:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Mes galime atskirti skaitmenis ir perrašyti taip:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Tai reiškia, kad bet kurį skaičių galima išreikšti jo skaitmenų suma ir 9 kartotiniu.
Taigi, jei imtume modulo su 9 kiekvienoje pusėje
abcd % 9 = (a + b + c + d) % 9 + 0Tai reiškia, kad likutis, kai abcd yra padalintas iš 9, yra lygus liekanai, kai jo skaitmenų suma (a + b + c + d) yra padalinta iš 9.
Jei pačią skaitmenų sumą sudaro daugiau nei vienas skaitmuo, šią sumą galime toliau išreikšti kaip jos skaitmenų sumą ir 9 kartotinį. Vadinasi, imant modulo 9, bus pašalintas 9 kartotinis, kol skaitmenų suma taps vienženkliu skaičiumi.
Dėl to bet kurio skaičiaus skaitmenų suma bus lygi jo modulio 9. Jei modulio operacijos rezultatas yra nulis, tai reiškia, kad vienaženklis rezultatas yra 9.
Norėdami sužinoti apie kodo įgyvendinimą, žr Duoto didelio sveikojo skaičiaus skaitmeninė šaknis (pakartotinė skaitmeninė suma).
