Armstrong Number

Q: מהי סיבוכיות הזמן של בדיקת מספר ארמסטרונג?

ב־ n יש בערך log n ספרות, לכל היותר 10 כאן. פירוק הספרות וחיפוש החזקה של כל אחת מהן בטבלה של עשר אפשרויות דורשים זמן O(log n) וזיכרון O(1) . חישוב מחדש של d^k באמצעות לולאה עבור כל ספרה הופך את הסיבוכיות ל־ O(log² n) , ועדיין מהיר בגודל הזה.

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

+10

מספר שלם חיובי הוא מספר ארמסטרונג כאשר הוא שווה לסכום הספרות שלו, כשכל אחת מהן מועלת בחזקה השווה למספר הספרות שלו. ל־153 יש שלוש ספרות, ו־1^3 + 5^3 + 3^3 = 153, ולכן הוא מספר ארמסטרונג. כתבו פונקציה שמקבלת את n ומחזירה true אם הוא מספר ארמסטרונג, ו־false אחרת.

פונקציה

isArmstrong(n: integer) → boolean

ninteger: המספר השלם החיובי שיש לבדוק
מחזירהboolean: נכון כאשר n שווה לסכום הספרות שלו, כאשר כל אחת מהן מועלת בחזקה השווה למספר הספרות

אילוצים

1 ≤ n ≤ 10⁹

דוגמאות

קלט: n = 153
פלט: true
הסבר: ל־153 יש 3 ספרות, לכן מעלים כל ספרה בחזקה שלישית: 1 + 125 + 27 = 153. הסכום מחזיר את המספר, לכן התשובה היא true.

קלט: n = 10
פלט: false
הסבר: ל־10 יש 2 ספרות, לכן מעלים בריבוע כל ספרה: 1 + 0 = 1, וזה לא 10. התשובה היא false.

קלט: n = 9474
פלט: true
הסבר: עם 4 ספרות החזקה היא 4: 6561 + 256 + 2401 + 256 = 9474, המספר עצמו, ולכן התשובה היא true.

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

שאלת המשך

רק 31 מספרי ארמסטרונג נמצאים בין 1 ל־10^9. האם תוכלו למנות את כולם בלי לבדוק מיליארד מספרים, אחד־אחד?

רמזים

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

נפתחו 0 מתוך 3

פתרון

ההגדרה היא האלגוריתם: מצא כמה ספרות יש ב־n, העלה כל ספרה בחזקה הזאת, חבר את התוצאות והשווה אותן ל־n. המלכודות הן במספרים. המעריך הוא מספר הספרות של n המסוים הזה, ולא 3 קבוע, והסכום יכול לחרוג ממספר שלם בן 32 סיביות: עבור 999999999 הוא 9 × 9^9 = 3486784401.

קרא את הספרות מהמחרוזת

האינטואיציה

המחרוזת העשרונית של n מספקת לך את שני הדברים הדרושים. האורך שלה הוא המעריך k, והתווים שלה הם הספרות. עבור 9474 יש במחרוזת 4 תווים, לכן מחברים את 9^4 + 4^4 + 7^4 + 4^4.

המר כל תו בחזרה לספרה שלו, העלה אותה בחזקת k והוסף אותה לסכום מצטבר. n הוא מספר ארמסטרונג בדיוק כאשר הסכום הסופי שווה ל-n.

שמור את הסכום במספר שלם בן 64 סיביות. n נכנס ב-32 סיביות, אבל הסכום לא בהכרח: 999999999 נותן 3486784401, שהוא מעל למגבלת 32 הסיביות של 2147483647. חישוב חזקה באמצעות לולאה של k כפלות עולה k צעדים לכל ספרה, ולכן הבדיקה היא O(k²) כאשר k הוא בערך log n. כאן נדרשות לכל היותר 100 כפלות, והמחרוזת צורכת k תווים של זיכרון.

אלגוריתם

המר את n למחרוזת עשרונית וקבע ש-k הוא האורך שלה.
אתחל את total לערך 0 מסוג 64 ביט.
עבור כל תו, המר אותו לספרה שלו d והוסף את d^k ל-total, תוך כפל מספרים שלמים במקום קריאה לפונקציית חזקה של נקודה צפה.
החזר האם total שווה ל-n.

def isArmstrong(n):
    digits = str(n)
    k = len(digits)
    total = 0
    for ch in digits:
        total += int(ch) ** k
    return total == n

קלפו את הספרות וחפשו את החזקות שלהן

האינטואיציה

חשבון אריתמטי לבדו עושה את אותה העבודה בלי מחרוזת. m % 10 היא הספרה האחרונה של m, וחלוקה שלמה ב־10 מסירה אותה, ולכן לולאה שמחלקת ב־10 עד שלא נשאר דבר סופרת את הספרות. 9474 הופך ל־947, 94, 9, 0: ארבעה צעדים, ולכן k = 4.

יש רק עשר ספרות, לכן יש לבנות טבלה powers[d] = d^k עבור d מ־0 עד 9 לפני שמחברים משהו. כך כל ספרה דורשת גישה אחת לטבלה במקום k פעולות כפל. זמן הבדיקה מצטמצם ל־O(log n), וגודל הטבלה קבוע — עשר, כלומר שימוש במקום של O(1).

הלולאה השנייה מפרקת שוב את הספרות ומוסיפה את powers[m % 10] לסכום. כל איבר הוא אפס או חיובי, לכן הסכום לעולם אינו קטן, וברגע שהוא עובר את n התשובה היא false. עבור 999999999 זה קורה אחרי שלוש ספרות, ב־3 × 387420489 = 1162261467. הטבלה עדיין דורשת 64 סיביות, כי ל־n = 10^9 יש עשר ספרות, ו־9^10 = 3486784401.

אלגוריתם

ספרו את הספרות של n על ידי חלוקת עותק שלו ב־10 עד שהוא מגיע ל־0; קראו למספר הספרות k.
מלאו את powers[d] = d^k עבור כל ספרה d מ־0 עד 9, במספרים שלמים בני 64 סיביות.
חלקו שוב עותק חדש של n ב־10, והוסיפו את powers[m % 10] אל total בכל שלב.
אם total עובר את n, החזירו מיד false.
אחרי הספרה האחרונה, החזירו האם total שווה ל־n.

def isArmstrong(n):
    # Count the digits: k is the exponent.
    k = 0
    m = n
    while m > 0:
        k += 1
        m //= 10
    # powers[d] = d^k for the ten possible digits.
    powers = [d ** k for d in range(10)]
    total = 0
    m = n
    while m > 0:
        total += powers[m % 10]
        if total > n:
            return False  # the total only grows
        m //= 10
    return total == n

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

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

מעריך קבוע של 3. הוא מקבל את 153 ואת 370, אך דוחה את 9474, ודוחה כל מספר חד־ספרתי שגדול מ־1, מכיוון ש־7^3 = 343.
סכום של 32 סיביות. הסכום של 999999999 הוא 3486784401, וזהו גם הערך בטבלה עבור 9^10. ב־C גלישת המספר הזו גורמת להתנהגות לא מוגדרת, ב־Java וב־C# המספר נעטף לערך שלילי, ובניית debug של Rust קורסת. השתמשו ב־long, ב־long long או ב־i64.
חזקות בנקודה צפה. pow ב־C ו־Math.pow ב־Java מחזירות ערך מסוג double. בחלק מסביבות הריצה של C הוחזר ערך מעט קטן ממספר שלם, למשל 24.999... עבור 5^2, והמרה מטיפוס זה קוטעת אותו ל־24. במקום זאת, הכפילו מספרים שלמים בתוך לולאה.
השוואה לערך הלא נכון. לולאות הספרות מחלקות את n עד שהוא מגיע ל־0, לכן עבדו על עותק והשוו את הסכום למספר המקורי.
סימון מדעי. ב־R, הערך של as.character(1e9) הוא "1e+09", שאורכו חמישה תווים, ולכן פתרון ב־R שמבוסס על מחרוזות מעצב את המספר באמצעות sprintf("%.0f", n).

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

מהו מספר ארמסטרונג?

מספר ארמסטרונג, המכונה גם מספר נרקיסיסטי, שווה לסכום הספרות שלו, כאשר כל אחת מהן מועלת בחזקת מספר הספרות. 153 הוא מספר כזה כי 1^3 + 5^3 + 3^3 = 153, ו-9474 הוא מספר כזה כי 9^4 + 4^4 + 7^4 + 4^4 = 9474. כל מספר בן ספרה אחת מתאים, כי d^1 = d.

כמה מספרי ארמסטרונג יש?

בבסיס 10 יש בדיוק 88 מספרים חיוביים מסוג ones, והגדול ביותר הוא בן 39 ספרות. הרשימה סופית, כי מספר בעל k ספרות הוא לפחות 10^(k-1), בעוד שסכום החזקות של ספרותיו הוא לכל היותר k × 9^k, ומ-61 ספרות ואילך הסכום לעולם לא יוכל להדביק אותו. בין 1 ל-10^9 יש 31.

למה בדיקת מספר ארמסטרונג זקוקה למספר שלם של 64 סיביות?

הקלט נכנס ב־32 ביטים, אבל סכום החזקות של הספרות יכול להיות גדול פי כמה מהמספר. 999999999 נותן 9 × 9^9 = 3486784401, שהוא גדול מ־2^31-1 = 2147483647. שם סכום ב־32 ביטים יגלוש, לכן יש לשמור את הסכום ואת החזקות בטיפוס של 64 ביטים.

מהי סיבוכיות הזמן של בדיקת מספר ארמסטרונג?

ב־n יש בערך log n ספרות, לכל היותר 10 כאן. פירוק הספרות וחיפוש החזקה של כל אחת מהן בטבלה של עשר אפשרויות דורשים זמן O(log n) וזיכרון O(1). חישוב מחדש של d^k באמצעות לולאה עבור כל ספרה הופך את הסיבוכיות ל־O(log² n), ועדיין מהיר בגודל הזה.

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

n = 153

צפוי

true