אתגר תכנותי: איזה מספר חסר

האתגר

נתון מערך `nums` המכיל n מספרים מובחנים בטווח [0, n]. עליך להחזיר את המספר היחיד בטווח שאינו מופיע במערך.

דוגמה 1:

Input: nums = [4, 2, 0, 1]
Output: 3

• המספר החסר הוא 3 כיוון שבטווח [0, 4] קיימים 5 מספרים, ורק המספר 3 חסר.

דוגמה 2:

Input: nums = [0,1,2]
Output: 3

• המספר החסר הוא 3 כיוון שהצפי הוא ל-4 מספרים ושלושת הראשונים מופיעים.

הצעה לפתרון

def missing_number(nums):
    xor_res = 0
    len_nums = len(nums)
    for idx in range(0, len_nums+1):
        xor_res ^= idx # XOR with numbers in range
        if idx < len_nums:
            xor_res ^= nums[idx] # XOR with numbers in nums
    return xor_res

נסביר:

האופרטור XOR (^) : משווה ביטים ומחזיר 1 אם רק אחד הביטים הוא 1 (והשני 0) ניתן ללמוד עוד על אופרטורים בינאריים במדריך עבודה עם מספרים בינאריים ואופרטורים bitwise.

הרעיונות הבאים יסייעו לנו בהבנת השימוש האופרטור XOR לצורך פתרון האתגר:

1. XOR של מספר עם עצמו שווה ל- 0.

   a XOR a = 0

   לדוגמה:

   1011 ^ 1011 = 0

2. כל מספר שנעשה לו XOR עם 0 ייתן תוצאה שהיא המספר המקורי.

   a XOR 0 = a

   לדוגמה:

   1011 ^ 0 = 1011

3. כשעושים XOR סדר האיברים לא משנה.

   a XOR b == b XOR a

   לדוגמה:

   1011 ^ 110 == 110 ^ 1011

נשתמש בתכונות לעיל לצורך פתרון יעיל של הבעיה:

1. נחשב את ה- XOR של כל המספרים בטווח [0, n].
2. נחשב את ה- XOR של כל המספרים במערך `nums`.
3. המספר החסר הוא התוצאה של XOR בין התוצאות של 1 ו-2.

• זה עובד כיוון שכל המספרים שמופיעים בשתי הקבוצות מבטלים זה את זה וכך משאירים רק את המספר החסר.

נבדוק:

# Test cases
test_cases = [
   [[3, 0, 1], 2],                # Missing number in the middle
   [[9, 6, 4, 2, 3, 5, 7, 0, 1], 8],  # Larger range
   [[0, 1], 2],                   # Missing number is the largest
   [[1, 2, 3], 0],                # Missing number is 0
   [[1], 0],                      # Single number, missing 0
   [[], 0]                        # Empty list, missing 0
]


print(f"{'Result'.ljust(10)}{'Expected'.ljust(10)}{'Conclusion'}")
print(f"{'-'*10}{'-'*10}{'-'*10}")

for nums, expected in test_cases:
   res = missing_number(nums)
   conclusion = "😄" if res == expected else "😭"
   print(f"{str(res).ljust(10)}{str(expected).ljust(10)}{conclusion}")


print("Finito Programa")

הפלט:

Result    Expected  Conclusion
------------------------------
2         2         😄 
8         8         😄  
2         2         😄  
0         0         😄  
0         0         😄  
0         0         😄  
Finito Programa

הערכת יעילות

• משך זמן ריצה: O(n)
  הלולאה רצה על כל איברי הטווח [0, n], ולכן הזמן פרופורציונלי לגודל הקלט.

• שימוש בזיכרון: O(1)
  לא נדרשת הקצאה נוספת מלבד משתנה xor_res.

סיכום

שימוש באופרטור XOR לפתרון בעיות תכנותיות כמו זו מבטיח פתרון פשוט, יעיל, וחסכוני.

מדריכים נוספים בסדרת הפייתון שעשויים לעניין אותך

עבודה עם מספרים בינאריים ואופרציות Bitwise בפייתון

אלגוריתם חיפוש בינארי - מהבנה ליישום

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים