Count Even Numbers
ניתנת לך רשימה לא ריקה של מספרים שלמים nums. החזר את מספר הערכים הזוגיים שבה. מספר הוא זוגי כאשר חלוקתו ב־2 אינה משאירה שארית, כולל 0 ומספרים שליליים כגון -4.
פונקציה
- numsinteger-array
- רשימת המספרים השלמים שיש לבדוק
- מחזירהinteger
- מספר הערכים הזוגיים ב-nums
אילוצים
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
דוגמאות
- קלט
- 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.
+12 בדיקות נסתרות בשליחה
שאלת המשך
מקבלים שאלות רבות מהצורה: כמה ערכים זוגיים נמצאים בין האינדקס l לאינדקס r? אחרי מעבר אחד על nums, האם אפשר לענות על כל שאלה בזמן O(1)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
מה נשאר כשמחלקים מספר זוגי ב-
2?ערך
xהוא זוגי בדיוק כאשרx % 2הוא0. שים לב: עבור מספר שלילי אי־זוגי, שפות מסוימות מחזירות-1כשארית, ולא1.התחילו מונה ב־
0, קראו כל ערך פעם אחת, והוסיפו1בכל פעם שהשארית בחלוקה ב־2היא0.
פתרון
הלולאה היא שורה אחת; בדיקת הזוגיות היא המקום שבו פתרונות נכשלים. בשפות רבות השארית של מספר שלילי היא שלילית, ולכן -3 % 2 הוא -1. הבדיקה x % 2 == 0 נכונה לכל סימן ובכל שפה, ומונה מצטבר אינו דורש זיכרון נוסף.
אספו את הערכים הזוגיים, ואז ספרו אותם
האינטואיציה
חלקו את המשימה לשני שלבים: בחרו את הערכים הזוגיים, ואז ספרו את מה שבחרתם. ערך x הוא זוגי כאשר x % 2 == 0. ברוב השפות יש פונקציית סינון שבונה את הרשימה החדשה בשורה אחת, והאורך שלה הוא התשובה. עבור [3, 8, 12, 5, 6] הרשימה המסוננת היא [8, 12, 6], ולכן התשובה היא 3.
זה נכון וקריא, אבל הרשימה החדשה צורכת זיכרון בגודל O(n), עד 5000 ערכים כאן, רק כדי לקרוא את האורך שלה פעם אחת. בערכים עצמם לא משתמשים שוב.
אלגוריתם
- בנה רשימה חדשה שתכיל כל
xמתוךnumsשעבורוx % 2 == 0. - החזר את האורך של הרשימה הזאת.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)ספור בעזרת מונה מתעדכן
האינטואיציה
השתמשו במונה במקום ברשימה. התחילו אותו ב־0, בדקו כל ערך פעם אחת, והוסיפו 1 כשהערך זוגי. כל ערך נבדק בדיוק פעם אחת, לכן הספירה מדויקת, והזיכרון היחיד שנדרש הוא מספר שלם אחד.
חשוב להקפיד על הבדיקה. ב־C, C++, Java, C#, JavaScript, Go, Rust, Swift ו־PHP, השארית מקבלת את הסימן של המספר, לכן -3 % 2 הוא -1, ולא 1. מספר זוגי משאיר שארית 0 ללא קשר לסימן שלו, לכן x % 2 == 0 תמיד נכון, בעוד שבדיקת אי־זוגיות שנכתבת כך: x % 2 == 1, מחמיצה כל מספר אי־זוגי שלילי. עבור [-4, -3, 0, 7] השאריות הן 0, -1, 0 ו־1, לכן המונה מסתיים בערך 2.
גם אפס נספר: 0 % 2 הוא 0, לכן 0 הוא זוגי.
אלגוריתם
- הגדירו את
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לעולם אינו נספר כאי־זוגי, ובסופו של דבר נספר כזוגי. - מתייחסים אל
0כאילו אינו זוגי ואינו אי־זוגי.0 = 2 × 0, ולכן הוא זוגי, והערך שמחזיר[0]הוא1. - כותבים את בדיקת הביטים כך:
x & 1 == 0. ב־C, ב־C++ וב־JavaScript, ל־==יש קדימות גבוהה יותר מל־&, ולכן הביטוי פירושוx & (1 == 0), שתוצאתו תמיד0ולכן הוא לא סופר דבר. כתבו(x & 1) == 0. - מתחילים את הלולאה באינדקס
1בשפה שמתחילה לספור מ־0, וכך מדלגים על הערך הראשון, או באינדקס0ב־Lua וב־R, שבהן הערך הראשון נמצא באינדקס1.
שאלות נפוצות4
איך בודקים בקוד אם מספר הוא זוגי?
בדקו אם השארית לאחר חלוקה ב־2 היא אפס: x % 2 == 0. זה עובד עבור מספרים חיוביים, מספרים שליליים ואפס בכל שפה נפוצה. דרך נוספת היא לבדוק את הסיבית הנמוכה ביותר באמצעות (x & 1) == 0, מכיוון שמספרים זוגיים מסתיימים בסיבית 0.
האם אפס הוא מספר זוגי?
כן. אפס חלקי 2 הוא 0 ללא שארית, ולכן הוא מתאים להגדרה של מספר זוגי. הוא גם נמצא בין המספרים האי־זוגיים -1 ו־1, בדיוק במקום שבו מספר זוגי אמור להיות.
למה x % 2 == 1 נכשל עבור מספרים שליליים?
ב-C, ב-C++, ב-Java, ב-C#, ב-JavaScript, ב-Go, ב-Rust, ב-Swift וב-PHP, השארית מקבלת את הסימן של המספר שמחלקים, ולכן -3 % 2 הוא -1. Python, Ruby, Dart, Lua ו-R מחזירות במקום זאת 1. בדיקה של x % 2 != 0 עבור מספר אי-זוגי ושל x % 2 == 0 עבור מספר זוגי מניבה את אותה תשובה בכולן.
מהי סיבוכיות הזמן של ספירת מספרים זוגיים במערך?
מעבר אחד עם מונה אורך O(n) ודורש O(1) שטח נוסף. צריך לבדוק כל ערך, לכן אין שיטה מהירה יותר מ־O(n). בניית רשימה מסוננת תחילה נותנת את אותה ספירה, אך משתמשת ב־O(n) זיכרון נוסף.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def countEvens(nums):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [3, 8, 12, 5, 6]
צפוי
3