Steps to Reduce a Number to Zero

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

הפעלת התהליך אורכת זמן O(log n) , משום שלפחות בכל צעד שני המספר נחצה. עבור n = 2^31 - 1 מדובר ב־ 61 צעדים. ספירת הספרות הבינאריות באמצעות הוראות ביט מובנות היא O(1) .

Q: מהי הנוסחה למספר הצעדים?

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

Q: איזה מספר הקטן מ־2^31 דורש את מספר הצעדים הרב ביותר?

2^31 - 1 , שהוא שלושים ואחד 1-ים בבינארי. הוא דורש 31 פעולות חיסור ו- 30 פעולות חלוקה ב-2, ובסך הכול 61 צעדים. אין מספר קטן יותר שיש בו מספר רב כל כך של ספרות וגם של 1-ים בו-זמנית.

Q: למה חלוקה בשניים זהה להזזה ימינה?

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

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

+10

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

פונקציה

numberOfSteps(n: integer) → integer

ninteger: המספר ההתחלתי
מחזירהinteger: מספר הצעדים עד שהמספר מגיע ל־0

אילוצים

0 ≤ n ≤ 2³¹ - 1

דוגמאות

קלט: n = 14
פלט: 6
הסבר: המספר עובר 14 → 7 → 6 → 3 → 2 → 1 → 0: שלוש חלוקות לחצי ושלוש פעולות חיסור, 6 צעדים.

קלט: n = 8
פלט: 4
הסבר: 8 → 4 → 2 → 1 → 0. חזקה של שתיים נחצית שלוש פעמים ודורשת חיסור אחד בסוף, 4 צעדים.

קלט: n = 123
פלט: 12
הסבר: 123 הוא 1111011 בבינארי: שבע ספרות ושישה 1-ים. ששת ה-1-ים עולים שש פעולות חיסור, ושש הספרות שמתחת ל-1 המוביל עולות שש פעולות חלוקה ב-2, 12 צעדים.

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

הפעלת הכלל כבר מהירה: כל חלוקה לחצי מקטינה את המספר בחצי, כך שגם 2^31 - 1 דורש רק 61 צעדים. החלק המעניין הוא לראות מה הכלל עושה לספרות הבינאריות. חלוקה לחצי מסירה את הספרה האחרונה, וחיסור 1 ממספר אי־זוגי הופך את ה־1 האחרון שלו ל־0. לכן התשובה היא מספר הספרות ועוד מספר הספרות 1, פחות אחת.

הפעל את התהליך

האינטואיציה

בצע את מה שההוראה אומרת. כל עוד n גדול מ־0, חלק אותו ב־2 אם הוא זוגי, החסר 1 אם הוא אי־זוגי, וספור את הצעד. עבור 14, הלולאה מבקרת בערכים 7, 6, 3, 2, 1 ו־0 — שישה צעדים.

הלולאה קצרה כי חיסור תמיד הופך מספר אי־זוגי לזוגי, ולכן לפחות בכל צעד שני מתבצעת חלוקה לשניים. מספר קטן מ־2^31 מתחלק לשניים לכל היותר 30 פעמים לפני שהוא מגיע ל־1, ועם חיסור אחד לפני כל חלוקה לשניים וחיסור אחד בסוף, הלולאה רצה לכל היותר 61 פעמים.

הקלט 0 אינו מצריך מקרה מיוחד: תנאי הלולאה נכשל מיד והתשובה היא 0.

אלגוריתם

הגדר את steps ל־0.
כל עוד n > 0: אם n זוגי, הגדר את n ל־n / 2, אחרת ל־n-1.
הוסף 1 ל־steps בכל פעם.
החזר את steps.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

ספרו את הספרות הבינאריות

האינטואיציה

צפו בתהליך בייצוג בינארי. 14 הוא 1110. חלוקה ב־2 מסירה את הספרה האחרונה: 111. חיסור 1 ממספר אי־זוגי מאפס את הספרה האחרונה שלו, 1: 110. לכן בכל שלב מסירים את הספרה האחרונה או הופכים 1 סופי ל־0.

עכשיו ספרו. יש לאפס כל 1 במספר פעם אחת, ולכן נדרשת פעולת חיסור אחת לכל 1. יש להסיר כל ספרה, ולכן נדרשת פעולת חלוקה אחת לכל ספרה, למעט הספרה המובילה: כשנותר רק 1, פעולת החיסור שמאפסת אותו כבר מביאה ל־0. לכן התשובה היא length - 1 + ones. עבור 14 = 1110, זה 4 - 1 + 3 = 6.

ל־Java, C, C++, Go, Rust ו־Swift יש פונקציות מובנות לשתי הספירות (ספירת אפסים מובילים וספירת ביטים דולקים), שמתקמפלות להוראה אחת ברוב המעבדים. בשאר השפות כותבים את n בייצוג בינארי וסופרים את התווים, או קוראים את הספרות באמצעות % 2; זו לולאה של לכל היותר 31 סבבים. החזירו תחילה 0 עבור n = 0: אין בו ביט 1 שיכול לשמש כעוגן לנוסחה.

אלגוריתם

אם n == 0, החזר 0.
מצא את length, מספר הספרות הבינאריות של n.
מצא את ones, מספר הביטים שערכם 1.
החזר length - 1 + ones.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

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

הכלל מורכב משתי שורות. הטעויות הן במקרי הקצה ובשגיאת off-by-one בנוסחה.

שוכחים את n = 0 בנוסחת הביטים. כשאין ספרות ואין 1-ים, length - 1 + ones נותן -1, וספירת האפסים המובילים של 0 עשויה להיות לא מוגדרת (__builtin_clz(0) ב-C).
סופרים חלוקה בחצי עבור הספרה המובילה. 1 הופך ל-0 באמצעות חיסור, לכן ל-8 = 1000 נדרשים 4 - 1 + 1 = 4 צעדים, ולא 5.
מאחדים שני צעדים לצעד אחד. כתיבה של n = (n-1) / 2 עבור מספר אי-זוגי מבצעת חיסור וחלוקה בחצי בבת אחת, ולכן צריך להוסיף 2 למונה, ולא 1. אחרת, התוצאה עבור 14 תהיה 4 במקום 6.
מבצעים לולאה כל עוד n > 1. כך עוצרים צעד אחד מוקדם מדי, כי הצעד האחרון הופך את 1 ל-0. הלולאה חייבת להמשיך עד ש-n יהיה 0.

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

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

הפעלת התהליך אורכת זמן O(log n), משום שלפחות בכל צעד שני המספר נחצה. עבור n = 2^31 - 1 מדובר ב־61 צעדים. ספירת הספרות הבינאריות באמצעות הוראות ביט מובנות היא O(1).

מהי הנוסחה למספר הצעדים?

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

איזה מספר הקטן מ־2^31 דורש את מספר הצעדים הרב ביותר?

2^31 - 1, שהוא שלושים ואחד 1-ים בבינארי. הוא דורש 31 פעולות חיסור ו-30 פעולות חלוקה ב-2, ובסך הכול 61 צעדים. אין מספר קטן יותר שיש בו מספר רב כל כך של ספרות וגם של 1-ים בו-זמנית.

למה חלוקה בשניים זהה להזזה ימינה?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

n = 14

צפוי