Sum of Digits
ניתן לך מספר שלם לא שלילי n. החזר את סכום הספרות העשרוניות שלו. לדוגמה, הספרות של 482 הן 4, 8 ו-2, ולכן התשובה היא 14.
פונקציה
- ninteger
- המספר השלם הלא־שלילי שאת ספרותיו מחברים
- מחזירהinteger
- סכום הספרות העשרוניות של n
אילוצים
0 ≤ n ≤ 231-1
דוגמאות
- קלט
- n = 9045
- פלט
- 18
- הסבר
- הספרות של
9045הן 9, 0, 4 ו־5, ו־9 + 0 + 4 + 5 = 18. האפס אינו מוסיף דבר, אך עדיין נחשב לספרה.
- קלט
- n = 7
- פלט
- 7
- הסבר
- מספר חד-ספרתי הוא סכום הספרות של עצמו, לכן
7נותן7.
+15 בדיקות נסתרות בשליחה
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
איך מוצאים את הספרה האחרונה של מספר באמצעות פעולת חשבון אחת?
הספרה האחרונה היא
n % 10, וחלוקה שלמה ב־10 מסירה אותה. כל זוג פעולות נותן לך ספרה אחת.שמרו על סכום מצטבר. כל עוד
nגדול מ־0, הוסיפו אליו אתn % 10וחלקו אתnב־10, תוך עיגול כלפי מטה.
פתרון
מספר לא נותן לך את הספרות שלו אחת אחת; צריך לפרק אותו. אפשר להפוך אותו לטקסט ולקרוא את התווים, או להשתמש בשתי פעולות החשבון שמסירות את הספרה האחרונה: n % 10 מחזירה אותה, וחלוקה שלמה ב־10 מסירה אותה. שתי השיטות דורשות צעד אחד לכל ספרה, המסומן ב־d להלן, וכאן d ≤ 10. הגרסה החשבונית אינה דורשת זיכרון נוסף.
קראו את הספרות כטקסט
האינטואיציה
כשכותבים מספר, הספרות שלו כבר גלויות לעיניכם. הופכים את n לטקסט עשרוני: 9045 הופך לארבעת התווים 9, 0, 4 ו־5, ואז עוברים על התווים ומוסיפים את הערך של כל אחד מהם.
תו עדיין אינו מספר. התו '4' מאוחסן כקוד 52, ולכן מנתחים אותו או מחסרים את הקוד של '0': '4' - '0' = 4. לתווי הספרות יש קודים עוקבים, ולכן החיסור הזה עובד עבור כל עשר הספרות.
בטקסט יש d תווים, אחד לכל ספרה, ולכן הלולאה אורכת זמן O(d), והטקסט עצמו דורש O(d) מקום נוסף.
אלגוריתם
- המר את
nלטקסט עשרוני. - הגדר
total = 0. - עבור כל תו, הוסף את ערך הספרה שלו ל־
total. - החזר את
total.
def sumOfDigits(n):
total = 0
for digit in str(n):
total += int(digit)
return totalהסר את הספרה האחרונה באמצעות % 10
האינטואיציה
אפשר לפרק מספר בלי להשתמש בטקסט. השארית של חלוקה ב־10 היא הספרה האחרונה: 9045 % 10 = 5. חלוקה שלמה ב־10 מסירה את הספרה הזאת: 9045 / 10 = 904 כאשר החלק השברי נזרק. חוזרים על הצמד, והספרות מתקבלות מימין לשמאל.
עבור 9045: מוסיפים 5 ומשאירים 904, מוסיפים 4 ומשאירים 90, מוסיפים 0 ומשאירים 9, מוסיפים 9 ומשאירים 0. הלולאה נעצרת ב־0 כשהסכום הוא 18. עבור n = 0 הלולאה לא מתבצעת כלל והתשובה היא 0, וזה נכון.
בכל שלב מוסרת ספרה אחת, ולכן יש d שלבים, זמן הריצה הוא O(d), ורק שני מספרים שלמים נשמרים בזיכרון, כלומר מקום בזיכרון של O(1). כל ערך ביניים קטן מ־n, ולכן לא יכולה להתרחש גלישה.
אלגוריתם
- הגדר את
total = 0. - כל עוד
n > 0, הוסף אתn % 10אלtotal. - חלק את
nב־10, תוך השמטת החלק השברי. - כאשר
nמגיע ל־0, החזר אתtotal.
def sumOfDigits(n):
total = 0
while n > 0:
total += n % 10 # last digit
n //= 10 # drop the last digit
return total
מלכודות ומקרי קצה
הלולאה קצרה, והטעויות קשורות לטיפוסים ולקלט הקטן ביותר.
- שימוש ב־
/במקום שבו השפה מתכוונת לחלוקה רגילה. ב־JavaScript, TypeScript, Lua, PHP ו־R,9045 / 10הוא904.5, ואז הלולאה מוסיפה שברים. עגלו כלפי מטה באמצעותMath.floorאוmath.floor; ב־Python השתמשו ב־//, ב־Dart ב־~/, ב־PHP ב־intdiv, וב־R ב־%/%. - הוספת תווים במקום ספרות. לתו
'7'יש קוד 55, לא 7. החסירו'0'או פענחו קודם את התו. - הרצת הלולאה כל עוד
n >= 10. הלולאה נעצרת כשהספרה המובילה עדיין בתוךnואינה מוסיפה אותה לעולם, ולכן9045נותן 9 במקום 18. הריצו את הלולאה כל עודn > 0, כך שהיא גם מחזירה 0 עבורn = 0. - הדפסת מספרים גדולים כטקסט ב־R.
as.character(100000)נותן"1e+05", ולא את שש הספרות של המספר. השתמשו ב־format(n, scientific = FALSE).
שאלות נפוצות4
מהי סיבוכיות הזמן של חיבור ספרותיו של מספר?
צעד אחד לכל ספרה, לכן O(d), כאשר d הוא מספר הספרות. למספר n יש בערך log10(n) + 1 ספרות, ולכן לעיתים קרובות כותבים את אותו חסם כך: O(log n). עבור מספר שלם בן 32 סיביות, מדובר ב-10 צעדים לכל היותר.
איך מקבלים את הספרות של מספר בלי להמיר אותו למחרוזת?
השתמש בשארית ובחלוקה שלמה ב־10. n % 10 היא הספרה האחרונה, וחלוקת n ב־10 תוך התעלמות מהשארית מסירה את הספרה הזאת. חזור על הפעולה עד ש־n מגיע ל־0, וכך תעבור על כל הספרות מימין לשמאל.
מהו השורש הדיגיטלי של מספר?
זה מה שמתקבל כשמחברים שוב ושוב את הספרות עד שנשארת ספרה אחת: 9045 נותן 18, ואז 9. עבור n חיובי, הערך שווה ל־1 + (n-1) % 9, כי לכל מספר ולסכום הספרות שלו יש אותה שארית בחלוקה ל־9.
איזו גרסה עדיפה, גרסת המחרוזת או הגרסה האריתמטית?
שתיהן הן O(d) ושתיהן נכונות. גרסת המחרוזת קצרה יותר לכתיבה בשפות רבות, אך יוצרת עותק של הספרות. הגרסה האריתמטית משתמשת בזיכרון נוסף של O(1) ומראה למראיין שאתה יודע איך % 10 ו־/ 10 מפרקים מספר, דבר שחוזר בבעיות של פלינדרומים והיפוך ספרות.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def sumOfDigits(n):
# כתבו כאן קודמקרה 1
מקרה 2
קלט
n = 9045
צפוי
18