Count Digits

Q: למה ל־0 יש ספרה אחת?

אפס נכתב בתו היחיד 0 , ולכן לייצוג העשרוני שלו יש ספרה אחת. קוד שסופר חלוקות כל עוד המספר גדול מ־0 לעולם אינו רץ עבור 0 ומחזיר 0. התחלת המונה ב־1 וחלוקה כל עוד המספר גדול או שווה ל־10 מטפלות בכך ללא מקרה מיוחד.

Q: האם אפשר להשתמש ב־log10 כדי לספור את הספרות של מספר?

עבור n חיובי, הספירה היא floor(log10(n)) + 1 , אבל הלוגריתם מחושב בנקודה צפה. הוא אינו מוגדר עבור 0, ובקרבת חזקה של עשר הוא עלול להתעגל בכיוון הלא נכון: log10(10^15-1) מתקבל בדיוק כ־15 בדיוקת כפולה. חלוקה שלמה נותנת את התשובה המדויקת בכל פעם.

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

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

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

+10

כתבו פונקציה שמקבלת מספר שלם לא שלילי n ומחזירה כמה ספרות יש לו כשכותבים אותו בבסיס 10 ללא אפסים מובילים. אפס נכתב בתור 0 יחיד, ולכן יש לו ספרה אחת.

פונקציה

countDigits(n: integer) → integer

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

אילוצים

0 ≤ n ≤ 2³¹-1

דוגמאות

קלט: n = 4096
פלט: 4
הסבר: חלוקה של מספר שלם ב־10 הופכת את 4096 ל־409, ל־40 ול־4. כך מוסרות שלוש ספרות ונשארת אחת, ולכן התשובה היא 4.

קלט: n = 0
פלט: 1
הסבר: 0 נכתב באמצעות ספרה אחת. לולאה שסופרת כל עוד המספר גדול מ־0 לעולם לא תפעל כאן ותחזיר 0 במקום 1.

קלט: n = 100
פלט: 3
הסבר: האפסים הם גם ספרות: 100 נכתב 1, 0, 0, לכן התשובה היא 3.

+16 בדיקות נסתרות בשליחה

שאלת המשך

האם אפשר לספור את הספרות בלי לולאה שרצה פעם אחת לכל ספרה, למשל באמצעות חיפוש בינארי בין חזקות של עשר?

רמזים

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

נפתחו 0 מתוך 3

פתרון

מספר הספרות הוא מספר הפעמים שאפשר לחלק ב־10 עד שנשארת ספרה אחת, ועוד אותה ספרה. הרעיון מתאים לשורה אחת; העבודה היא בטיפול במקרי הקצה. ל־0 יש ספרה אחת, הספירה משתנה בין 9 ל־10, ונוסחה המבוססת על לוגריתם נכשלת ב־0 ובחישובי נקודה צפה, מעט מתחת לחזקות גדולות של עשר.

כתבו את המספר כמחרוזת וספרו את התווים

האינטואיציה

השפה שלך כבר יודעת לכתוב את n בבסיס עשרוני. בקש ממנה את המחרוזת הזאת וספור את התווים: 4096 הופך ל־"4096", ארבעה תווים. 0 הופך ל־"0", תו אחד, ולכן אפס אינו דורש מקרה מיוחד.

ההמרה מחלקת ב־10 בתוך הספרייה, פעם אחת לכל ספרה, כך שהעבודה היא O(log n). המחרוזת מכילה תו אחד לכל ספרה, כלומר נדרש זיכרון נוסף של O(log n), עד 10 תווים כאן.

העיצוב חייב להיות עשרוני רגיל. ב־R, הפקודה as.character(1e5) מחזירה "1e+05", חמישה תווים עבור מספר בן שש ספרות, ולכן יש לעצב באמצעות sprintf("%.0f", n). ב־Lua 5.3 ואילך, tostring(4096.0) משאירה את .0, בעוד string.format("%d", n) כותבת את המספר השלם בכל הגרסאות.

אלגוריתם

המירו את n למחרוזת עשרונית באמצעות פונקציה שאינה עוברת לעולם לכתיב מדעי.
ספרו את התווים במחרוזת.
החזירו את הספירה הזו. עבור 0, המחרוזת היא "0", לכן התשובה היא 1 בלי בדיקה נוספת.

def countDigits(n):
    return len(str(n))

חלקו ב־10 עד שתישאר ספרה אחת

האינטואיציה

חלוקה של מספר שלם ב־10 מסירה את הספרה האחרונה: 4096 / 10 הוא 409. כל חלוקה מסירה ספרה אחת, לכן מספר החלוקות הדרושות כדי להגיע לספרה אחת, ועוד אחת עבור הספרה האחרונה, הוא התשובה. עבור 4096 נדרשות שלוש חלוקות (409, 40, 4), ולכן יש בו 4 ספרות.

התחל את הספירה מ־1 וחלק כל עוד n ≥ 10. התחלה מ־1 מציינת שלכל מספר יש לפחות ספרה אחת, וזה בדיוק הכלל עבור 0. הגרסה שאנשים כותבים ראשונה, שסופרת כל עוד n > 0 החל מ־0, מחזירה 0 עבור n = 0 ודורשת בדיקה נפרדת.

הלולאה רצה פעם אחת עבור כל ספרה אחרי הראשונה, לכל היותר 9 פעמים עבור 2147483647, ולכן זמן הריצה שלה הוא O(log n). היא משתמשת במונה אחד ומשנה את העותק שלה של n, ולכן המקום הנוסף הוא O(1).

אלגוריתם

הגדר את count = 1, עבור הספרה שתמיד נמצאת שם.
כל עוד n ≥ 10, חלק את n ב־10 בחלוקה שלמה והוסף 1 ל־count.
כשנותרת ספרה אחת, החזר את count.

def countDigits(n):
    count = 1  # every number, 0 included, has at least one digit
    while n >= 10:
        n //= 10
        count += 1
    return count

מלכודות ומקרי קצה

כל באג בבעיה הזאת נמצא בקצה.

ספירה מ־0 כל עוד n > 0. זה עובד לכל מספר חיובי ומחזיר 0 עבור n = 0.
שימוש ב־floor(log10(n)) + 1. זה נכשל עבור 0, שבו הלוגריתם הוא מינוס אינסוף, וגם עבור ערכים גדולים שקצת קטנים מחזקה של עשר: בדיוק כפול, log10(10^15-1) מתעגל בדיוק ל־15, ולכן הנוסחה מחזירה 16 ספרות במקום 15.
חלוקה ממשית בלולאה שרצה כל עוד n > 0. ב־JavaScript, ב־Lua, ב־PHP וב־R, האופרטור / משאיר את החלק השברי, ולכן 4096 מתקרב ל־0 במשך 328 צעדים לפני שהוא מגיע אליו. השתמשו ב־Math.floor, ב־math.floor, ב־intdiv או ב־%/%.
סימון מדעי בגרסת המחרוזת: ב־R, המספר 100000 נכתב כך: "1e+05".
סימן מינוס שנספר כספרה. הקלט כאן לעולם אינו שלילי, אבל ל־String(-42) יש שלושה תווים, ולכן גרסה עבור מספרים שליליים מחשבת קודם את הערך המוחלט.

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

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

חלק אותו ב־10 בחלוקה שלמה עד שתישאר ספרה אחת, תוך ספירת החלוקות, והוסף 1 עבור הספרה האחרונה. 4096 הופך ל־409, 40, 4: שלוש חלוקות, כלומר 4 ספרות. הלולאה משתמשת בזיכרון נוסף של O(1).

למה ל־0 יש ספרה אחת?

אפס נכתב בתו היחיד 0, ולכן לייצוג העשרוני שלו יש ספרה אחת. קוד שסופר חלוקות כל עוד המספר גדול מ־0 לעולם אינו רץ עבור 0 ומחזיר 0. התחלת המונה ב־1 וחלוקה כל עוד המספר גדול או שווה ל־10 מטפלות בכך ללא מקרה מיוחד.

האם אפשר להשתמש ב־log10 כדי לספור את הספרות של מספר?

עבור n חיובי, הספירה היא floor(log10(n)) + 1, אבל הלוגריתם מחושב בנקודה צפה. הוא אינו מוגדר עבור 0, ובקרבת חזקה של עשר הוא עלול להתעגל בכיוון הלא נכון: log10(10^15-1) מתקבל בדיוק כ־15 בדיוקת כפולה. חלוקה שלמה נותנת את התשובה המדויקת בכל פעם.

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

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

n = 4096

צפוי