logo

TechCodeview

Hľadanie súčtu číslic čísla, kým sa súčet nestane jednou číslicou

Vyskúšajte to na GfG Practice ' title=

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



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



  1. Spočítajte číslice : Začnite sčítaním všetkých číslic daného čísla.
  2. Skontrolujte výsledok : Ak je súčet jednociferné číslo (t. j. menej ako 10), zastavte a vráťte ho.
  3. 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++ 
// 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(log10n), pretože iterujeme cez číslice čísla.
Pomocný priestor: O(1)

pivot pandy

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

To 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