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

מציאת סכום ספרות של מספר עד שהסכום הופך לחד-ספרתי
נסה את זה ב-GfG Practice

בהינתן מספר 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(log 10 n) בזמן שאנו חוזרים על ספרות המספר.
מרחב עזר: 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.
כדי לדעת על יישום קוד עיין שורש דיגיטלי (סכום דיגיטלי חוזר) של המספר השלם הגדול הנתון