Задачи с собеседований: число

Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.

С толку сбивает только одна фраза «упорядоченная последовательность», она-то и может натолкнуть на использование сортировки для решения данной задачи. Программисты довольно часто пользуются готовыми библиотеками и фреймворками, поэтому при решении задач автоматом обдумываешь, что будешь использовать из библиотеки. Для многих программистов единственным очевидным решением является сортировка полученной последовательности и далее поэлементное сравнение исходной и отсортированной последовательностей до первого несовпадения. Можно подсчитать сложность такого решения: O(NlogN) сложность сортировки плюс линейная сложность поиска. Хм, может подойти к решению как-то иначе?

Давайте забудем о том, что последовательность упорядочена. Обе последовательности различаются всего одним числом, а значит, чтобы его найти нужно из суммы элементов исходной последовательности вычесть сумму полученной.