Предложите алгоритм для поиска числа, заменённого на 0, в массиве из 100 случайно расположенных чисел от 1 до 100. Оцените временную и пространственную сложность.

Сумма чисел от 1 до 100 равна 5050. Вычтите фактическую сумму массива: разность и будет числом, заменённым на ноль. Алгоритм использует один проход и постоянную дополнительную память.

def missing_number(values):
    return 100 * 101 // 2 - sum(values)

Время O(n), дополнительная память O(1), при условии что каждое число 1…100 встречалось ровно один раз и заменён только один элемент. Альтернатива — XOR всех ожидаемых и фактических значений. Если возможны дубликаты, несколько замен или значения вне диапазона, этот ответ уже не гарантирован: вход нужно валидировать или решать другую задачу.