задачка про числа

Понравилась задача для предварительного интервью программиста (phone screen), которую увидел в Твиттере с пометкой "самая сложная задача предварительного интервью, что я когда-либо видел". Автор поста написал,. что ему 30 минут на нее дали, и интервью он не прошел.

Все числа от одного до N, кроме одного, перемешаны в случайном порядке и записаны подряд без пробелов. Вы получаете эту длинную строку и должны найти, какого числа не хватает.

Я когда прочитал, сначала немного подумал и решил, что напишу запись, мол, прикольно, но не слишком тяжело, надо немного креативно подумать. Потом подумал еще и сел написать код, а когда написал, решил, что да, в качестве предварительного интервью это очень брутально.

P.S. Рад обсуждениям возможных решений, но не надо длинных цитат из ИИ, мы и так все понимаем, что можно его спросить.