קצת על סיבוכיות

כשסיבוכיות באה לידי מעשה

נתבונן בשאלה הבאה אשר ממחישה בצורה טובה איך ניתן לייעל אלגוריתם.

נתון מערך באורך N אשר מכיל מספרים מאפס עד N כולל, ואף מספר אינו חוזר פעמיים.
פירוש הדבר הוא שקיים בדיוק מספר אחד בין אפס ל-N שלא מופיע במערך.
מצאו את המספר!


ובפשטות, ממשו את הפונקציה findMissingNumber:

    public static void main(String[] args) {
        // N is 6
        int[] array = new int[] {0, 1, 2, 6, 4, 3};
        
        int missingNumber = findMissingNumber(array);
        System.out.println("The missing number is: " + missingNumber); // 5
    }