logo

TechCodeview

Etsitään luvun numeroiden summaa, kunnes summasta tulee yksinumeroinen

Kokeile sitä GfG Practicessa ' title=

Kun kokonaisluku n on annettu, meidän on löydettävä toistuvasti sen numeroiden summa, kunnes tuloksesta tulee yksinumeroinen luku.

Esimerkkejä:

Syöte: n = 1234
Lähtö: 1
Selitys:
Vaihe 1: 1 + 2 + 3 + 4 = 10
Vaihe 2: 1 + 0 = 1



Syöte: n = 5674
Lähtö: 4
Selitys:
Vaihe 1: 5 + 6 + 7 + 4 = 22
Vaihe 2: 2 + 2 = 4

Sisällysluettelo

[Naiivi lähestymistapa] Lisäämällä toistuvasti numeroita

Lähestymistapa keskittyy digitaalisen roon laskemiseen t luvusta, joka on tulosta summaamalla numerot toistuvasti, kunnes saadaan yksinumeroinen arvo. Näin se toimii käsitteellisesti:



  1. Summaa numerot : Aloita lisäämällä kaikki annetun numeron numerot.
  2. Tarkista tulos : Jos summa on yksinumeroinen luku (eli alle 10), lopeta ja palauta se.
  3. Toista prosessi : Jos summa on edelleen enemmän kuin yksi numero, toista prosessi numeroiden summalla. Tämä jatkuu, kunnes saavutetaan yksinumeroinen summa.
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));

Lähtö 
1

Aika monimutkaisuus: O(log10n) kun iteroimme luvun numeroiden yli.
Aputila: O(1)

[Odotettu lähestymistapa] Matemaattisen kaavan käyttäminen

Tiedämme, että jokainen luku desimaalijärjestelmässä voidaan ilmaista sen numeroiden summana kerrottuna 10:n potenssilla. Esimerkiksi luku, joka esitetään abcd voidaan kirjoittaa seuraavasti:

abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0

Voimme erottaa numerot ja kirjoittaa tämän uudelleen seuraavasti:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)

Tämä tarkoittaa, että mikä tahansa luku voidaan ilmaista sen numeroiden summana plus 9:n kerrannainen.
Joten jos otamme modulon 9:n kummallakin puolella
abcd % 9 = (a + b + c + d) % 9 + 0

Tämä tarkoittaa, että jäännös, kun abcd jaetaan 9:llä, on yhtä suuri kuin jäännös, jossa sen numeroiden summa (a + b + c + d) jaetaan 9:llä.



Jos itse numeroiden summa koostuu useammasta kuin yhdestä numerosta, voimme edelleen ilmaista tämän summan sen numeroiden summana plus 9:n kerrannainen. Näin ollen modulo 9:n ottaminen eliminoi luvun 9 kerrannaisen, kunnes numeroiden summasta tulee yksinumeroinen luku.

Tämän seurauksena minkä tahansa luvun numeroiden summa on yhtä suuri kuin sen modulo 9. Jos modulo-operaation tulos on nolla, yksinumeroinen tulos on 9.
Lisätietoja koodin käyttöönotosta on kohdassa Annetun suuren kokonaisluvun digitaalinen juuri (toistuva digitaalinen summa).