Count Digits
בהינתן מספר שלם אי־שלילי n, החזירו את מספר הספרות שלו כשהוא נכתב בבסיס 10 ללא אפסים מובילים. אפס נכתב כספרה אחת, 0, ולכן יש לו ספרה אחת.
פונקציה
- ninteger
- המספר השלם הלא־שלילי למדידה
- מחזירהinteger
- מספר הספרות העשרוניות ב־n
אילוצים
0 ≤ n ≤ 231-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.
שאלת המשך
האם תוכל לספור את הספרות בלי לולאה שרצה פעם אחת לכל ספרה, למשל באמצעות חיפוש בינארי בין החזקות של עשר?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
מה קורה למספר הספרות כשמחלקים מספר ב־10 ומשליכים את השארית?
כל חלוקה של מספר שלם ב־10 מסירה בדיוק ספרה אחת מהסוף. ספרו כמה חלוקות נדרשות כדי להגיע לספרה אחת.
אתחל מונה ל-1 וחלק ב-10 כל עוד המספר גדול או שווה ל-10, תוך הוספת 1 בכל פעם. התחלה ב-1 נותנת גם את התשובה הנכונה עבור
0.
פתרון
כל חלוקה שלמה ב־10 מסירה ספרה אחת. ספור את החלוקות עד שנותרת ספרה אחת, ואז הוסף אחת עבור אותה ספרה. הבאגים נמצאים בקצוות: ל־0 יש ספרה אחת, ונוסחת לוגריתם נכשלת עבור 0 וגם מעט מתחת לחזקות גדולות של 10.
כתבו את המספר כטקסט וספרו את התווים
האינטואיציה
השפה שלך כבר כותבת את n בבסיס עשרוני. בקש את המחרוזת הזאת וספור את התווים שלה: 4096 הופך ל־"4096", ארבעה תווים, ו־0 הופך ל־"0", כך שאין צורך במקרה מיוחד עבור אפס.
ההמרה מבצעת חלוקה אחת לכל ספרה, לכן גם הזמן וגם הזיכרון הנוסף הם O(log n), לכל היותר 10 תווים כאן.
אלגוריתם
- המר את
nלמחרוזת העשרונית שלו באמצעות פונקציה שאינה עוברת לעולם לכתיב מדעי. - ספור את התווים במחרוזת.
- החזר את המספר הזה. עבור
0המחרוזת היא"0", לכן התשובה היא1ללא בדיקה נוספת.
def countDigits(n):
return len(str(n))חלקו ב־10 עד שתישאר ספרה אחת
האינטואיציה
התחל את הספירה ב־1 וחלק ב־10 כל עוד n ≥ 10, והוסף 1 בכל חלוקה. התחלה ב־1 מציינת שלכל מספר יש לפחות ספרה אחת, וזה בדיוק הכלל עבור 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, שבו הלוגריתם הוא מינוס אינסוף, וגם עבור10^15-1, שבו דיוק כפול מעגל את הלוגריתם בדיוק ל־15 והנוסחה מציינת שיש 16 ספרות. - חלוקה ממשית ב־JavaScript, Lua, PHP או R, שבה
/משאיר את השבר. לולאה שרצה כל עודn > 0תתבצע אז 328 פעמים עבור4096. השתמשו ב־Math.floor, ב־math.floor, ב־intdivאו ב־%/%. - סימון מדעי בגרסת המחרוזת. ב־R,
as.character(1e5)נכתב כך:"1e+05"; השתמשו ב־sprintf("%.0f", n). ב־Lua 5.3 ואילך,tostring(4096.0)משאיר את ה־.0; השתמשו ב־string.format("%d", n).
שאלות נפוצות3
מהי סיבוכיות הזמן של ספירת ספרות?
למספר n יש floor(log10(n)) + 1 ספרות, והלולאה מבצעת חילוק אחד לכל ספרה, ולכן היא פועלת בזמן O(log n) ובמרחב O(1). עבור מספר שלם בן 32 סיביות, מדובר ב-10 צעדים לכל היותר.
האם תוכל להשתמש ב־log10 כדי לספור את הספרות של מספר?
עבור n חיובי, הספירה היא floor(log10(n)) + 1, אבל הלוגריתם מחושב בנקודה צפה. הוא אינו מוגדר עבור 0, וקרוב לחזקה של עשר הוא עלול להתעגל בכיוון הלא נכון: log10(10^15-1) מתקבל בדיוק כ־15 בדיוקת double. חלוקה של מספרים שלמים תמיד מדויקת.
איך סופרים את הספרות של מספר שלילי?
קודם מוצאים את הערך המוחלט, ואז סופרים כרגיל. ב־String(-42) יש שלושה תווים, כי סימן המינוס אינו ספרה. עבור המספר השלם הקטן ביותר ב־32 סיביות, יש למצוא את הערך המוחלט בטיפוס של 64 סיביות, כי הוא אינו נכנס ב־32 סיביות.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def countDigits(n):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
n = 4096
הפלט הצפוי
4