logo

מציאת סכום ספרות של מספר עד שהסכום הופך לחד-ספרתי

נסה את זה ב-GfG Practice ' title=

בהינתן מספר n שלם עלינו למצוא שוב ושוב את סכום הספרות שלו עד שהתוצאה הופכת למספר חד ספרתי.

דוגמאות:

קֶלֶט: n = 1234
תְפוּקָה: 1
הֶסבֵּר:
שלב 1: 1 + 2 + 3 + 4 = 10
שלב 2: 1 + 0 = 1



קֶלֶט: n = 5674
תְפוּקָה: 4
הֶסבֵּר:
שלב 1: 5 + 6 + 7 + 4 = 22
שלב 2: 2 + 2 = 4

תוכן עניינים

[גישה נאיבית] על ידי הוספת ספרות שוב ושוב

הגישה מתמקדת בחישוב הרווח הדיגיטלי ט של מספר שהוא תוצאה של סיכום הספרות שוב ושוב עד לקבלת ערך חד ספרתי. הנה איך זה עובד מבחינה רעיונית:



  1. סכם את הספרות : התחל בהוספת כל הספרות של המספר הנתון.
  2. בדוק את התוצאה : אם הסכום הוא מספר חד ספרתי (כלומר פחות מ-10) עצור והחזר אותו.
  3. חזור על התהליך : אם הסכום עדיין יותר מספרה בודדת חזור על התהליך עם סכום הספרות. זה נמשך עד שמגיעים לסכום חד ספרתי.
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)); 

תְפוּקָה
1

מורכבות זמן: O(log10n) בזמן שאנו חוזרים על ספרות המספר.
מרחב עזר: O(1)

[גישה צפויה] שימוש בנוסחה מתמטית

אנו יודעים שכל מספר במערכת העשרונית יכול לבוא לידי ביטוי כסכום ספרותיו כפול בחזקות 10. למשל מספר המיוצג כ abcd ניתן לכתוב כך:

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

נוכל להפריד בין הספרות ולשכתב זאת כ:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)

זה מרמז שניתן לבטא כל מספר כסכום הספרות שלו בתוספת כפולה של 9.
אז אם ניקח מודולו עם 9 בכל צד
abcd % 9 = (a + b + c + d) % 9 + 0

משמעות הדבר היא שהשאר כאשר מחלקים abcd ב-9 שווה לשאר כאשר סכום הספרות שלו (a + b + c + d) מחולק ב-9.



אם סכום הספרות עצמו מורכב מיותר מספרה אחת נוכל לבטא עוד יותר את הסכום הזה כסכום הספרות שלו בתוספת כפולה של 9. כתוצאה מכך לקיחת מודולו 9 תבטל את הכפולה של 9 עד שסכום הספרות יהפוך למספר חד ספרתי.

כתוצאה מכך סכום הספרות של כל מספר יהיה שווה למודולו 9 שלו. אם התוצאה של פעולת המודולו היא אפס זה מציין שהתוצאה החד-ספרתית היא 9.
כדי לדעת על יישום קוד עיין שורש דיגיטלי (סכום דיגיטלי חוזר) של המספר השלם הגדול הנתון