Counting Bits

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

הפתרון הטוב ביותר רץ בזמן O(n): כל אחד מ־ n+1 האיברים מתקבל מאיבר קודם אחד באמצעות חיבור אחד. ספירת הביטים של כל מספר בנפרד אורכת O(n log n). בשתי השיטות נדרשת זיכרון O(1) מעבר למערך הפלט.

Q: האם קיימת נוסחת נסיגה אחרת בסיבוכיות O(n) לספירת ביטים?

כן. i & (i-1) מאפס את ביט ה־1 הנמוך ביותר של i , ולכן bits[i] = bits[i & (i-1)] + 1 עבור כל i שגדול מ־0 או שווה לו. עבור 12 ( 1100 ), 12 & 11 הוא 8 ( 1000 ), שיש בו 1 אחד, ולכן ב־12 יש שניים.

Q: האם אפשר להשתמש בפונקציית popcount מובנית?

קריאה לאחת מהן עבור כל מספר, כמו Integer.bitCount ב-Java או __builtin_popcount ב-C וב-C++, מניבה תשובה נכונה. מראיינים בדרך כלל מבקשים את הגרסה בלעדיהן, כי מטרת הבעיה היא לעשות שימוש חוזר בתשובות שכבר חישבת.

קלמניפולציית ביטים תכנון דינמי

+10

בהינתן מספר שלם n שאינו שלילי, החזר מערך של n+1 איברים, שבו האיבר i הוא מספר הספרות 1 בייצוג הבינארי של i, עבור כל i מ-0 עד n.

פונקציה

countBits(n: integer) → integer-array

ninteger: המספר האחרון לספירה, 0 או יותר
מחזירהinteger-array: מערך של n+1 ספירות, שבו הערך במקום i הוא מספר הביטים 1 ב־i

אילוצים

0 ≤ n ≤ 2 × 10⁴

דוגמאות

קלט: n = 2
פלט: [0, 1, 1]
הסבר: בייצוג בינארי, 0 הוא 0, 1 הוא 1 ו-2 הוא 10: אין אחדות, ואז אחת, ואז אחת.

קלט: n = 5
פלט: [0, 1, 1, 2, 1, 2]
הסבר: 3 הוא 11 ו־5 הוא 101, בכל אחד מהם יש שתי ספרות 1; 4 הוא 100, עם אחת. יחד עם 0, 1 ו־2 מהדוגמה הראשונה, הספירות הן 0, 1, 1, 2, 1, 2.

שאלת המשך

האם תוכל למלא את כל המערך בזמן O(n), בלי להשתמש בפונקציה מובנית שסופרת ביטים ובלי לספור כל מספר מחדש?

רמזים

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

נפתחו 0 מתוך 3

פתרון

ספירה של כל מספר מחדש חוזרת על עבודה: 13 הוא 1101, הביטים של 6 (110) עם ספרה אחת נוספת בסוף. מלאו את התשובות בסדר עולה, וכל איבר משתמש מחדש באיבר קטן יותר בתוספת אחת.

ספור את הביטים של כל מספר

האינטואיציה

ספרו ישירות את כל סיביות ה־1 של כל מספר: הוסיפו x & 1 למונה, הזיזו את x ימינה בסיבית אחת, ועצרו ב־0. עבור 13 (1101) הסיביות מתקבלות כך: 1, 0, 1, 1, ולכן הספירה היא 3.

למספר עד n יש בערך log2 n ספרות בינאריות, ולכן זמן הריצה הוא O(n log n): בערך 20,000 × 15 = 300,000 צעדים עבור n = 2 × 10^4.

אלגוריתם

התחל רשימת תוצאות ריקה.
עבור כל i מ־0 עד n, הגדר את count ל־0 ואת x ל־i.
כל עוד x גדול מ־0, הוסף את x & 1 ל־count והזז את x ימינה בביט אחד.
הוסף את count לתוצאה.
החזר את התוצאה.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

בנה על מחצית המספר

האינטואיציה

הזזה של i ימינה באחד מסירה את הספרה הבינארית האחרונה שלו, ו־i & 1 היא הספרה הזאת. לכן ל־i יש את הספרות 1 של i >> 1 בתוספת הספרה האחרונה שלו: bits[i] = bits[i >> 1] + (i & 1).

עבור כל i שערכו 1 או יותר, i >> 1 קטן מ־i, ולכן מילוי המערך משמאל לימין, החל מ־bits[0] = 0, פירושו שהערך שקוראים ממנו תמיד מוכן. עבור n = 5: bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

כל איבר דורש הזזה אחת, פעולת AND אחת וחיבור אחד: זמן O(n) וללא זיכרון נוסף מעבר לפלט.

אלגוריתם

צור מערך bits של n+1 אפסים. bits[0] נשאר 0.
עבור i מ־1 עד n, הגדר את bits[i] ל־bits[i >> 1] + (i & 1).
החזר את bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

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

החזרת n איברים במקום n+1. עבור n = 0 התשובה היא [0].
קדימות אופרטורים. ב-Python, ב-C, ב-Java וב-JavaScript, ל-+ יש קדימות גבוהה יותר מל-&, לכן bits[i >> 1] + i & 1 פירושו (bits[i >> 1] + i) & 1. השאירו את הסוגריים סביב (i & 1).
חיפוש של bits[i-1] במקום bits[i >> 1]. אין כלל פשוט שמשותף למספרים סמוכים: 7 הוא 111 עם שלושה 1-ים, ו-8 הוא 1000 עם אחד.
ב-Lua וב-R, מערכים מתחילים ב-1, לכן ספירת ה-i נמצאת באינדקס i+1, והחיפוש של i >> 1 באינדקס floor(i/2) + 1. ב-Lua 5.1 אין אופרטור הזזה, ולכן מחלקים ב-2 באמצעות math.floor(i / 2).

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

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

הפתרון הטוב ביותר רץ בזמן O(n): כל אחד מ־n+1 האיברים מתקבל מאיבר קודם אחד באמצעות חיבור אחד. ספירת הביטים של כל מספר בנפרד אורכת O(n log n). בשתי השיטות נדרשת זיכרון O(1) מעבר למערך הפלט.

האם קיימת נוסחת נסיגה אחרת בסיבוכיות O(n) לספירת ביטים?

כן. i & (i-1) מאפס את ביט ה־1 הנמוך ביותר של i, ולכן bits[i] = bits[i & (i-1)] + 1 עבור כל i שגדול מ־0 או שווה לו. עבור 12 (1100), 12 & 11 הוא 8 (1000), שיש בו 1 אחד, ולכן ב־12 יש שניים.

האם אפשר להשתמש בפונקציית popcount מובנית?

קריאה לאחת מהן עבור כל מספר, כמו Integer.bitCount ב-Java או __builtin_popcount ב-C וב-C++, מניבה תשובה נכונה. מראיינים בדרך כלל מבקשים את הגרסה בלעדיהן, כי מטרת הבעיה היא לעשות שימוש חוזר בתשובות שכבר חישבת.

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

בדיקה #1

בדיקה #2

ארגומנט

n = 2

הפלט הצפוי

[0, 1, 1]