logo

TechCodeview

Egy szám számjegyeinek összegének megkeresése, amíg az összeg egyjegyűvé nem válik

Próbáld ki a GfG Practice-n ' title=

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.

Kat timpf

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 = 1



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

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:



  1. Adja össze a számjegyeket : Kezdje a megadott szám összes számjegyének összeadásával.
  2. Ellenőrizze az eredményt : Ha az összeg egyjegyű szám (azaz 10-nél kisebb), állítsa le, és adja vissza.
  3. 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++ 
// 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(log10n) ahogy iteráljuk a szám számjegyeit.
Kiegészítő tér: O(1)

iteráló térkép java

[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 + 0

Ez 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.



összehasonlítani a java karakterláncaival

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