Задача на написание кода: найти наименьшее натуральное число, отсутствующее в массиве

Задача: найти наименьшее натуральное число (больше 0), отсутствующее в массиве.

Пример решения на Go с линейной сложностью и использованием дополнительной памяти:

package main

import "fmt"

func findMissingPositive(nums []int) int {
    n := len(nums)
    present := make([]bool, n+1) // индексы от 0 до n

    for _, num := range nums {
        if num > 0 && num <= n {
            present[num] = true
        }
    }

    for i := 1; i <= n; i++ {
        if !present[i] {
            return i
        }
    }

    return n + 1
}

func main() {
    arr := []int{3, 4, -1, 1}
    fmt.Println(findMissingPositive(arr)) // Выведет 2
}

Идея: отмечаем, какие числа от 1 до n встречаются, затем ищем первое отсутствующее. Если все есть, ответ n+1.