Happy Number

Q: למה התהליך תמיד מגיע ל-1 או ללולאה?

מספר עם d ספרות ממופה לכל היותר ל־ 81 × d , ולכן מספרים גדולים מצטמצמים במהירות: כל מספר התחלתי עד 2^31-1 יורד מתחת ל־1000 אחרי צעד אחד, ומספר קטן מ־1000 ממופה לכל היותר ל־243. המסלול מוגבל לפחות מ־1000 ערכים, ולכן הוא חייב לחזור על אחד מהם, ומאותו רגע הוא מחזורי. 1 הוא המספר היחיד שממופה לעצמו.

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

השלב הראשון קורא את O(log n) הספרות של n . כל ערך מאוחר יותר קטן מ־1000, והמסלול חוזר על עצמו בתוך 20 מספרים לכל היותר, ולכן זמן הריצה הכולל הוא O(log n) . הגרסה עם קבוצת הגיבוב שומרת את המספרים שבהם ביקרנו; הגרסה של Floyd משתמשת ב־ O(1) מקום.

קלמצביע מהיר ואיטי גיבוב

+10

התחל ממספר שלם חיובי n והחלף אותו בסכום ריבועי הספרות שלו, שוב ושוב. לדוגמה, 12 הופך ל־1² + 2² = 5. אם התהליך מגיע ל־1, n הוא מספר שמח; אחרת הוא חוזר שוב ושוב במסלול מעגלי דרך מספרים שאינם כוללים אף פעם את 1. החזר true אם n הוא מספר שמח ו־false אם לא.

פונקציה

isHappy(n: integer) → boolean

ninteger: המספר השלם החיובי לבדיקה
מחזירהboolean: true אם חזרה על חישוב סכום ריבועי הספרות מגיעה ל-1, false אם היא נכנסת ללולאה אינסופית

אילוצים

1 ≤ n ≤ 2³¹-1

דוגמאות

קלט: n = 7
פלט: true
הסבר: 7 הופך ל־49, ואז 4² + 9² = 97, ואז 130, ואז 10, ואז 1. התהליך מגיע ל־1, ולכן 7 הוא מספר שמח.

קלט: n = 2
פלט: false
הסבר: 2 הופך ל־4, 16, 37, 58, 89, 145, 42, 20 ואז שוב ל־4. משם אותם שמונת המספרים חוזרים לנצח ולעולם לא מגיעים אל 1.

קלט: n = 100
פלט: true
הסבר: 1² + 0² + 0² = 1, לכן 100 מגיע ל־1 אחרי צעד אחד.

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

שאלת המשך

איך הייתם סופרים במהירות את המספרים השמחים מ-1 עד 10^6, תוך שימוש חוזר בתשובות עבור מספרים שמתחת ל-1000 במקום להתחיל את החישוב מחדש עבור כל מספר?

רמזים

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

נפתחו 0 מתוך 3

פתרון

המסלול לא יכול להימשך עד אינסוף. מספר בן 10 ספרות ממופה לערך שאינו עולה על 10 × 81 = 810, ומספר קטן מ־1000 ממופה לערך שאינו עולה על 3 × 81 = 243, ולכן אחרי צעד אחד המסלול נשאר בין פחות מ־1000 ערכים וחייב להגיע ל־1 או לחזור על מספר. כך הבעיה הופכת לזיהוי מחזור: זוכרים את מה שכבר ראית, או מפעילים הולך איטי והולך מהיר ובודקים אם הם נפגשים.

זכור כל מספר שראית

האינטואיציה

עבור על הרצף ושמור כל מספר בקבוצת גיבוב. לפני שתמשיך ממספר כלשהו, בדוק אם הוא כבר נמצא בקבוצה. עבור 2, הקבוצה מתמלאת ב-2, 4, 16, 37, 58, 89, 145, 42 ו-20, והערך הבא הוא 4, שכבר נמצא בה: המסלול נסגר בלולאה בלי להגיע ל-1, ולכן 2 אינו מספר שמח. הגעה ל-1 מסיימת את המסלול עם true.

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

המסלול קצר. הצעד הראשון קורא את הספרות O(log n) של n, וכל ערך מאוחר יותר קטן מ-1000, כך שאף מסלול אינו מבקר ביותר מ-20 מספרים שונים לפני שהוא מגיע ל-1 או חוזר על עצמו. הקבוצה מכילה את המספרים האלה. קוד C משתמש במערך דגלים של 1000 רשומות בתור הקבוצה ומתחיל לרשום אחרי הצעד הראשון, כשכל ערך קטן מ-1000.

אלגוריתם

צרו קבוצת גיבוב ריקה seen.
כל עוד n אינו 1, החזירו false אם n נמצא ב-seen.
אחרת, הוסיפו את n ל-seen והחליפו את n בסכום ריבועי הספרות שלו.
כשהלולאה מסתיימת, n הוא 1: החזירו true.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

הולכים מהירים ואיטיים (זיהוי מעגלים של Floyd)

האינטואיציה

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

אם הלולאה אינה מכילה את 1, שני ההולכים מסתובבים בה, ובכל סיבוב fast מתקדם בצעד אחד על פני slow, כך שהפער מצטמצם באחד עד שהם עומדים על אותו מספר. עבור 2 הם נפגשים ב־42 לאחר שבעה סיבובים. אם המסלול מגיע ל־1, fast מגיע לשם ראשון ונשאר, כי הסכום עבור 1 הוא 1. לכן עוצרים כאשר fast הוא 1 או כשההולכים נפגשים, ומשיבים אם fast הוא 1.

עבור 7, slow עובר דרך 7, 49, 97, בעוד fast עובר דרך 49, 130, 1, והלולאה נעצרת כש־fast נמצא על 1. מספר הסיבובים הוא לכל היותר כפולה קטנה של אורך המסלול, ולכן זמן הריצה זהה לזה של הגרסה עם הקבוצה, והזיכרון הנדרש הוא שני מספרים שלמים.

אלגוריתם

כתבו פונקציית עזר שמחזירה את סכום ריבועי הספרות של מספר.
הגדירו slow = n והגדירו את fast כמספר שנמצא צעד אחד אחרי n.
כל עוד fast אינו 1 ו-slow שונה מ-fast, קדמו את slow צעד אחד ואת fast שני צעדים.
החזירו האם fast הוא 1.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

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

חישוב הספרות קצר. רוב הטעויות נוגעות למועד שבו הלולאה נעצרת.

המשיכו בלולאה עד שהערך הוא 1, בלי תנאי יציאה נוסף. עבור 2 הלולאה לא תסתיים לעולם.
התחילו את slow ואת fast באותו מספר ובדקו slow != fast לפני הצעד הראשון. הלולאה לא תרוץ, ו-7 יתקבל כמספר שאינו שמח. התחילו את fast צעד אחד קדימה, או הזיזו את שניהם לפני ההשוואה הראשונה.
החזירו slow == 1 בגרסת Floyd. fast מגיע ל-1 ראשון והלולאה נעצרת מיד, בעוד slow עדיין יכול להיות על 97.
חברו את הספרות במקום את ריבועיהן, או העלו בריבוע את המספר כולו. עבור 12 הערך הבא הוא 1² + 2² = 5, ולא 3 ולא 144.
הכריזו ש-n אינו מספר שמח בכל פעם שהמצביעים נפגשים. 1 ממופה לעצמו, ולכן המצביעים נפגשים גם ב-1; בדקו היכן הם נפגשו, או עצרו ברגע ש-fast הוא 1.

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

למה התהליך תמיד מגיע ל-1 או ללולאה?

מספר עם d ספרות ממופה לכל היותר ל־81 × d, ולכן מספרים גדולים מצטמצמים במהירות: כל מספר התחלתי עד 2^31-1 יורד מתחת ל־1000 אחרי צעד אחד, ומספר קטן מ־1000 ממופה לכל היותר ל־243. המסלול מוגבל לפחות מ־1000 ערכים, ולכן הוא חייב לחזור על אחד מהם, ומאותו רגע הוא מחזורי. 1 הוא המספר היחיד שממופה לעצמו.

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

השלב הראשון קורא את O(log n) הספרות של n. כל ערך מאוחר יותר קטן מ־1000, והמסלול חוזר על עצמו בתוך 20 מספרים לכל היותר, ולכן זמן הריצה הכולל הוא O(log n). הגרסה עם קבוצת הגיבוב שומרת את המספרים שבהם ביקרנו; הגרסה של Floyd משתמשת ב־O(1) מקום.

למה כל המספרים הלא מאושרים מגיעים בסופו של דבר ל-4?

בדיקה של כל מספר קטן מ־1000 מראה שיש בדיוק לולאה אחת שאינה מגיעה ל־1: 4, 16, 37, 58, 89, 145, 42, 20 וחזרה ל־4. מכיוון שכל מספר התחלתי יורד מתחת ל־1000, כל מספר שאינו שמח מגיע אליה. פתרון יכול לעצור ברגע שהוא מגיע ל־4, אבל הדבר מסתמך על עובדה שתצטרך להצדיק בריאיון; קבוצת המספרים והשיטה של Floyd אינן דורשות ידע כזה.

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

בשניהם בודקים אם מעקב אחר חץ אחד מכל פריט מוביל אי פעם לפריט שכבר ביקרנו בו. ב-Happy Number החץ הוא סכום ריבועי הספרות; ברשימה מקושרת הוא המצביע לפריט הבא. לכן ההולכים המהירים והאיטיים של Floyd פותרים את שתי הבעיות תוך שימוש בזיכרון קבוע.

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

n = 7

צפוי

true