logo

TechCodeview

Skaičiaus skaitmenų sumos radimas, kol suma tampa vienženkle

Išbandykite GfG praktikoje ' title=

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

Š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:



  1. Sumuokite skaičius : Pradėkite pridėdami visus nurodyto skaičiaus skaitmenis.
  2. Patikrinkite rezultatą : Jei suma yra vienaženklis skaičius (ty mažiau nei 10), sustokite ir grąžinkite.
  3. 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++ 
// 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(log10n) 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 + 0

Tai 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).