Count Even Numbers

Q: איך בודקים בקוד אם מספר הוא זוגי?

בדקו אם השארית לאחר חלוקה ב־ 2 היא אפס: x % 2 == 0 . זה עובד עבור מספרים חיוביים, מספרים שליליים ואפס, אפילו בשפות שבהן -3 % 2 הוא -1 . אפשר גם לבדוק את הסיבית הנמוכה ביותר באמצעות (x & 1) == 0 .

Q: האם אפס הוא מספר זוגי?

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

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

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

מתחיליםמערכים ומחרוזות מתמטיקה וסימולציה

+10

בהינתן רשימה לא ריקה של מספרים שלמים nums, יש להחזיר כמה מהערכים בה זוגיים. מספר הוא זוגי כאשר חלוקתו ב־2 אינה משאירה שארית, וזה כולל את 0 ואת המספרים השליליים, כגון -4.

פונקציה

countEvens(nums: integer-array) → integer

numsinteger-array: רשימת המספרים השלמים שיש לבדוק
מחזירהinteger: מספר הערכים הזוגיים ב־nums

אילוצים

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

דוגמאות

קלט: nums = [3, 8, 12, 5, 6]
פלט: 3
הסבר: ‏8, ‏12 ו־6 מתחלקים ב־2 ללא שארית; ‏3 ו־5 אינם מתחלקים. התשובה היא 3.

קלט: nums = [-4, -3, 0, 7]
פלט: 2
הסבר: -4 = 2 × (-2) וגם 0 = 2 × 0, לכן שניהם זוגיים. -3 ו-7 הם אי-זוגיים, והספירה היא 2.

קלט: nums = [1, 9, 15]
פלט: 0
הסבר: 1, 9 ו־15 הם כולם אי־זוגיים, לכן התשובה היא 0.

שאלת המשך

שואלים אותך שאלות רבות: כמה ערכים זוגיים נמצאים בין האינדקס l לאינדקס r? אחרי מעבר אחד על nums, האם תוכל לענות על כל אחת מהן בזמן O(1)?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

אספו את הערכים הזוגיים, ואז ספרו אותם

האינטואיציה

בחר את הערכים הזוגיים באמצעות מסנן, ואז החזר את אורך התוצאה. עבור [3, 8, 12, 5, 6] הרשימה המסוננת היא [8, 12, 6], ולכן התשובה היא 3.

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

אלגוריתם

בנה רשימה חדשה שמכילה כל x שב-nums שעבורו מתקיים x % 2 == 0.
החזר את האורך של הרשימה הזאת.

def countEvens(nums):
    evens = [x for x in nums if x % 2 == 0]
    return len(evens)

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

האינטואיציה

שמרו מונה במקום רשימה, והוסיפו 1 עבור כל ערך שעבורו x % 2 == 0. מספר זוגי משאיר שארית 0 ללא קשר לסימן שלו, ולכן הבדיקה מתקיימת עבור -4 ועבור 0 בכל שפה. בדיקה לזיהוי מספרים אי־זוגיים שנכתבת x % 2 == 1 אינה עובדת כך: ב-C, ב-Java, ב-JavaScript וברוב השפות הדומות ל-C, השארית מקבלת את הסימן של המספר, ולכן -3 % 2 הוא -1.

מעבר אחד ומספר שלם אחד: זמן O(n), מקום O(1).

אלגוריתם

הגדר את count ל-0.
עבור בלולאה על כל ערך x ב-nums.
אם x % 2 == 0, הוסף 1 ל-count.
לאחר הלולאה, החזר את count.

def countEvens(nums):
    count = 0
    for x in nums:
        if x % 2 == 0:  # 0 also works for negatives, where the remainder can be -1
            count += 1
    return count

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

ספירת הערכים האי-זוגיים באמצעות x % 2 == 1 והחסרתם מהאורך. בשפות דמויות C, הביטוי -3 % 2 הוא -1, ולכן [-3] מחזיר 1 במקום 0.
התייחסות אל 0 כאילו הוא אינו זוגי ואינו אי-זוגי. 0 = 2 × 0, ולכן [0] מחזיר 1.
כתיבת בדיקת הביטים כך: x & 1 == 0. ב-C, ב-C++ וב-JavaScript, ל-== יש קדימות גבוהה יותר מאשר ל-&, ולכן משמעות הביטוי היא x & (1 == 0), שתוצאתו תמיד 0 ולכן הוא אינו סופר דבר. יש לכתוב (x & 1) == 0.

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

איך בודקים בקוד אם מספר הוא זוגי?

בדקו אם השארית לאחר חלוקה ב־2 היא אפס: x % 2 == 0. זה עובד עבור מספרים חיוביים, מספרים שליליים ואפס, אפילו בשפות שבהן -3 % 2 הוא -1. אפשר גם לבדוק את הסיבית הנמוכה ביותר באמצעות (x & 1) == 0.

האם אפס הוא מספר זוגי?

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

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

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

def countEvens(nums):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

nums = [3, 8, 12, 5, 6]

הפלט הצפוי