Как быстро определить что множество содержит все натуральные числа от N до M?

Question

[Сергей]

Имеется множество натуральных чисел от N до M.
М и N могут меняться во времени.
Как можно быстро определить, содержит ли данное множество все натуральные числа от N до M не прибегая к полному перебору всех элементов (точнее полный перебор в начале сделать можно, но потом при добавлении\удалении элементов это делать не нужно).

Т.е. например, изначально в множестве есть:
1,3 - критерий должен говорить что это не полное множество.
потом мы добавили 4
1,3,4 - опять не полное.
добавили 2
1,2,3,4 -- полное.
Здесь критерий должен сказать что мы в множестве имеем все натуральные числа от 1 до 4 включительно.

P.S. На ум приходит сравнение суммы элементов с суммой арифметической прогрессии между N(min элемент) и M(max элемент). Но насколько это надежный способ?

P.S.S В множестве могут быть только уникальные элементы

Comments

[uvelichitel]

Если элементы уникальные, то даже не обязательно сумму, достаточно просто количество.

Answer 1

[evgeniy_lm]

M-N+1= количество членов множества
разумеется при условии, что в множестве нет одинаковых членов.
Иначе только сортировка и поштучный поиск первого недостающего члена

Answer 2

[x67]

тут в первую очередь надо определиться со структурой данных. Массив? надо сортировать. Огромный массив - надо долго сортировать.
А так как множество натуральных чисел, пусть будет массив bool значений, при том индекс элемента массива - натуральное число, а значение элемента - его наличие в множестве. В таком случае нам все равно придется перебрать m-n значений, но не надо будет ничего сортировать, да и реализовано может быть прямо ассемблерной вставочкой, что должно существенно ускорить код.
Другой вариант если мы все таки не хотим перебирать - создать сложную структуру, в которой множество меняется путем добавления или удаления "островов" натуральных чисел или островов их отсутствия.
В таком случае предположим у нас есть множество 0-inf(1-inf, если вы натуральный нулененавистник). Пусть мы убрали из него числа 4 и 5, тогда добавим в структуру остров [4:5]. Убрали еще числа 7-1110, также добавляем выколотый остров 7:1110. Добавили 666, значит или делим остров или добавляем остров другого типа(в зависимости от реализации). Когда множество будет готово,нужно будет сравнить его со всеми островами и в зависимости от их типа, если M,N принадлежит острову натуральных чисел или между M и N отсутствуют выколотые острова, мы делаем вывод о том, содержит ли множество все эти числа. Теоретически такой подход выигрышен при стремлении размерности множества к бесконечности и при конечном количестве островов. На практике, я бы блеснул этими решениями на собеседовании и больше никогда не возвращался бы к таким задачам)