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

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

כיצד נוכל אחרי שעברנו על סדרת המספרים לדעת מי המספר שהופיע ביותר ממחצית הפעמים?

יש לי הצעה. מופיעה בלבן.

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

בדיעבד, אפשר להמשיל זאת ל"מזיגה" של כל המספרים לאותו מקום כשכל מספר שונה מהמספר הנפוץ מבטל ממנו אחד. מספר הביטולים יהיה קטן ממספר המופעים של המספר ולכן יוותרו מופעים שלא בוטלו.

****** 

כן. זו התשובה. הייתי מתקן תיקון קטן, אם כי אני לא בטוח אם זה משנה (בלבן על לבן):

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