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

נתונה מטריצה בת $\displaystyle n$ עמודות ו$\displaystyle m=2^{n}-1$ שורות. כל כניסה במטריצה היא 0 או 1, ולכן כל שורה מתארת מספר בינרי בעל $\displaystyle n$ ביטים. השורות אינן מסודרות בסדר ידוע, אך ידוע שאין שתי שורות זהות. מכאן נובע שחסרה שורה להשלמת כל $\displaystyle 2^{n}$ המספרים האפשריים בעלי $\displaystyle n$ ביטים.

דוגמה: עבור $\displaystyle n=2$, ייתכן שהשורה הראשונה היא המערך [0, 1] (המתאר בבינרית את המספר 1), השורה השנייה היא המערך [1, 1] (המתאר בבינרית את המספר 3), והשורה השלישית היא המערך [0, 0] (המתאר בבינרית את המספר 0). השורה החסרה היא המערך [1, 0] (המתאר בבינרית את המספר 2).

אנא תאר אלגוריתם המקבל מטריצה כזו, ומדפיס את השורה החסרה. נסה להגיע לאלגוריתם שסיבוכיותו $\displaystyle \Theta (m)$.

רמז נסה להפוך את הבעיה לבעיה קטנה בחצי (בערך) בזמן לינארי.