Ayao "Alqualos" Kuroyuki (ayao) wrote,
Ayao "Alqualos" Kuroyuki
ayao

Задача: из N чисел одного не хватает, какого?

Димариус приволок ещё одну задачу. Не в пример проще игры Витгофа, конечно. Любой ламер-программист её должен решить достаточно быстро. Димариус утверждал - даётся минута. Я потратил по заверениям публики секунд 15, значит на самом деле около полминуты. Из них, правда, секунд 15 я потратил на нытьё, что никаким лимитам времени я подчиняться не хочу ^_^

Значит, я ещё не отупел окончательно.

Задача действительно проста: дано множество всех целых чисел от 1 до N. Из этого множества дан неупорядоченный набор чисел количеством N-1 штук. Одного не хватает, стало быть. Задача - определить какого. Сложность алгоритма - O(n), то есть порядка N шагов, если по-русски. Так что вариант "перебирать числа от 1 до N и каждое искать в заданном наборе" - не прокатит, так как тут порядок O(n^2).
Tags: think
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments