Sum of Digits

Q: מהי סיבוכיות הזמן של חיבור ספרותיו של מספר?

צעד אחד לכל ספרה, לכן O(d) , כאשר d הוא מספר הספרות. למספר n יש בערך log10(n) + 1 ספרות, ולכן לעיתים קרובות כותבים את אותו חסם כך: O(log n) . עבור מספר שלם בן 32 סיביות, מדובר ב-10 צעדים לכל היותר.

Q: איך מקבלים את הספרות של מספר בלי להמיר אותו למחרוזת?

השתמש בשארית ובחלוקה שלמה ב־10. n % 10 היא הספרה האחרונה, וחלוקת n ב־10 תוך התעלמות מהשארית מסירה את הספרה הזאת. חזור על הפעולה עד ש־ n מגיע ל־0, וכך תעבור על כל הספרות מימין לשמאל.

מתחיליםמתמטיקה וסימולציה

+10

ניתן לך מספר שלם לא שלילי n. החזר את סכום הספרות העשרוניות שלו. לדוגמה, הספרות של 482 הן 4, 8 ו-2, ולכן התשובה היא 14.

פונקציה

sumOfDigits(n: integer) → integer

ninteger: המספר השלם הלא־שלילי שאת ספרותיו מחברים
מחזירהinteger: סכום הספרות העשרוניות של n

אילוצים

0 ≤ n ≤ 2³¹-1

דוגמאות

קלט: n = 9045
פלט: 18
הסבר: הספרות של 9045 הן 9, 0, 4 ו־5, ו־9 + 0 + 4 + 5 = 18. האפס אינו מוסיף דבר, אך עדיין נחשב לספרה.

קלט: n = 7
פלט: 7
הסבר: מספר חד-ספרתי הוא סכום הספרות של עצמו, לכן 7 נותן 7.

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

מספר לא נותן לך את הספרות שלו אחת אחת; צריך לפרק אותו. אפשר להפוך אותו לטקסט ולקרוא את התווים, או להשתמש בשתי פעולות החשבון שמסירות את הספרה האחרונה: 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).

שאלות נפוצות3

מהי סיבוכיות הזמן של חיבור ספרותיו של מספר?

צעד אחד לכל ספרה, לכן 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.

def sumOfDigits(n):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנט

n = 9045

הפלט הצפוי