Верхняя граница четырехзначных последовательностей в пи

Question

Если это не тот сайт SE по этому вопросу, пожалуйста, дайте мне знать.

Друг поделился этим вопросом интервью, который он получил по телефону, который я пытался решить самостоятельно. Я перефразирую:

Значение pi вплоть до n цифры в виде строки дается.

Как найти все повторяющиеся последовательности из 4 цифр в этой строке?

Эта часть кажется довольно простой. Добавьте 4 последовательности символов в хеш-таблицу, увеличивая по одному символу за раз. Проверьте, существует ли текущая последовательность из 4 символов перед вставкой в ​​хеш-таблицу. Если так, то вы нашли дубликат. Сохраните это где-нибудь и повторите процесс. Мне сказали, что это более или менее правильно.

У меня есть проблема по второму вопросу:

Какова верхняя граница?

n = 10,000,000 был пример.

Мой алгоритм фона по общему признанию очень ржавый. Сначала я подумал, что верхняя граница должна быть как-то связана с n, но мне сказали, что это не так.

Как мне рассчитать это?

РЕДАКТИРОВАТЬ:

Я также был бы открыт для решения, которое игнорирует ограничение, которое верхняя граница не связана с n, Либо приемлемо.

Answer 1

Есть только 10000 возможных последовательностей из четырех цифр (0000 в 9999), так что в какой-то момент вы обнаружите, что каждая последовательность была продублирована, и нет необходимости обрабатывать дальнейшие цифры.

Если вы предполагаете, что pi является абсолютно равномерным генератором случайных чисел, то каждая новая обрабатываемая цифра приводит к новой последовательности, и после примерно 20 000 цифр вы найдете дубликаты для всех 10 000 последовательностей. При условии pi не является идеальным, вам может потребоваться значительно больше цифр, прежде чем вы продублируете все последовательности, но 100 000 будет разумным предположением для верхней границы.

Кроме того, поскольку существует всего 10 000 возможностей, вам не нужен хеш-стол. Вы можете просто использовать массив из 10000 счетчиков, (int count[10000]) и увеличьте счетчик для каждой найденной последовательности.

Answer 2

Верхняя граница вашего решения - это размер хеш-таблицы, которую вы можете поместить в память.

Альтернативный метод состоит в том, чтобы генерировать все последовательности и сортировать их. Тогда дубликаты будут соседними и их легко обнаружить. Как правило, вы можете вписать больше в линейную структуру данных, чем в хеш-таблицу, и если вы все еще исчерпываете память, вы можете сортировать на / с диска.

Изменить: если "верхняя граница" означает O(n) алгоритма, который должен быть легко выяснить.