מספר שמופיע מספר אי-זוגי של פעמים
שיעור 10 מתוך 17 בקורס מניפולציה על ביטים של Coddy.
זכור את האתגר שפתרת בשיעור "אופרטור XOR", שבו השתמשנו בתכונות של XOR. השאלה שנפתור בשיעור הזה דומה למדי לאתגר הזה. לכן, הבעיה שנבחן היא:
מצאו את האיבר שמופיע מספר אי־זוגי של פעמים במערך הנתון.
תקבלו מערך שמכיל כמה איברים שלמים. מבין האיברים האלה, כל שאר האיברים מופיעים מספר זוגי של פעמים, פרט לאיבר אחד.
נניח שיש לנו מערך int Arr[11] = { 2, 5, 6, 6, 6, 4, 5, 2, 5, 4, 5}.
במערך הזה,
- '2' מופיע פעמיים (זוגי).
- '5' מופיע ארבע פעמים (זוגי).
- '6' מופיע שלוש פעמים (אי־זוגי).
- '4' מופיע פעמיים (זוגי).
לכן, המספר '6' הוא זה שמופיע מספר אי־זוגי של פעמים. וזה מה שעלינו למצוא בשאלה: המספר שמופיע מספר אי־זוגי של פעמים במערך.
כפי שראינו בשיעור על אופרטור "XOR", עבור מספר 'x',
- x ⊕ x = 0 (כאשר הסמל '⊕' מייצג את פעולת XOR)
- x ⊕ 0 = x
לכן, אם נשתמש בתכונה הראשונה, כל האיברים שמופיעים מספר זוגי של פעמים יתאפסו בעת ביצוע XOR, ובעזרת התכונה השנייה, יישאר לנו המספר שהופיע מספר אי־זוגי של פעמים.
לכן, למעשה, ביצוע XOR על כל איברי המערך ייתן לנו בסופו של דבר את התוצאה. וזהו, זה הפתרון לבעיה. קל, נכון?
סיבוכיות הזמן של הבעיה הזאת היא O(n), כי עלינו לעבור על כל המערך ולבצע XOR על כל איבריו.
אתגר
קלהשלימו את הפונקציה "OddElement" כדי להחזיר את האיבר שהופיע מספר אי־זוגי של פעמים במערך הנתון. השתמשו באופרטור XOR כדי לפתור את הבעיה.
נסו בעצמכם
#include <iostream>
#include <vector>
using namespace std;
int OddElement(vector<int> arr) {
// כתבו כאן קוד
}כל השיעורים ביחידה מניפולציה על ביטים
2אלגוריתמים על ביטים
חזקה של 2מספר שמופיע מספר אי-זוגי של פעמיםמספר הביטים הדולקיםסיבוב הביטים של מספר Iסיבוב הביטים של מספר IIתרגלו בעצמכם: קומפיילר C++ אונליין