אתה סוכם את המספרים מ-1 עד n (זה n פעולות)
אתה מתחיל להחסיר את הסכום הזה מכל ה-n+1 איברים (זה n+1 פעולות)
המספר שנותר בערכו המוחלט זה המספר המבוקש.
סה"כ (O(n פעולות.
אם תרצה גם אלגוריתם ב-C זה שתי שניות

פתרתי את זה על ידי סכום כול האינדקסים עד n
סכום כול המערך n+1 ואז חיסור של סכום המערך בסכום האינדקסים
והמספר הנותר זה המספר שמופיע פעמיים

איך זה?

טוב אני קודם כל אסביר את הפתרון:
חילקתי את כל המספרים ל- log n קבוצות, כאשר בכל קבוצה N/log N איברים.
וההפרש בין כל איבר לאיבר הוא log n.
לדוגמא N=8, Log N = 3
אז יש את ה-3 קבוצות הבאות:
1,4,7
2,5,8
3,6

(ברמת העיקרון לפתרון החידה אפשר לחלק לאיזו קבוצות שאנו רוצים,
העיקר שמספר הקבוצות יהיה מספר האיברים במערך, ושיהיה היגיון בין המספרים, לדוגמא, אם אני לא טועה, גם ההגדרה הבאה נכונה:
1,2,3
4,5,6
7,8)

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

אני אתן דוגמא שתפשט את זה, אם ככה ייראה המערך הגדול:
{1,3,2,4,5,6,2,2,4}
ככה ייראה הקטן:
{21,13,11}

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

M= Log(n);
for i:=1 to n+1 do
Begin
	j:=1;
	Ezer:=Array
	while Ezer>=(M) do
	Begin
		Ezer:=Ezer-M;	
		inc(j);
	End;
	If ((ShortArray) div (10^(j-1)) <> 0) and ((((ShortArray) div (10^(j-1)) mod 10) = 1) then
		return (Array);
	else ShortArray:=ShortArray+10^(j-1);
End;