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

הסבר פתרון:

נבחין כי אם יש מערך בגודל x התשובות האפשריות:

1 עד x או x+1.

במקרה זה האינדקסים של המערך יהיו 0 עד x-1.

כלומר האינדקסים יכולים להוות אינדיקציה מי הפתרון ומי לא.

שלב ראשון:

סריקת המערך: כל ערך בין 1 ל x+1 יוחלף עם המיקום המתאים לו באופן הבא:

1 יותאם למיקום 0.

2 יותאם למיקום 1

... וכך הלאה

הערך x יותאם ל x-1.

לא נתייחס לערכים שליליים, אפס ולמי שגדול מ x.

לאחר מכן נבצע סריקה ונבדוק האם באינדקס 0 יש 1, אם לא נחזיר 1. אם כן נבדוק האם באינדקס 1 יש 2: אם לא נחזיר 2 וכך הלאה.

אם לא החזרנו דבר, נחזיר x+1.

סיבוכיות

O(n)

בעצם אנחנו מבצעים פעמיים סריקה של המערך.

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

לכן בסך הכל הסיבוכיות היא n.