Разработайте алгоритм, позволяющий найти k-e число из упорядоченного числового ряда, в разложении элементов которого на простые множители присутствуют только 3, 5 и 7

По условию задачи любое число этого ряда должно представлять собой произведение 3a · 5b · 7c.

Давайте посмотрим на список чисел, удовлетворяющих нашим требованиям:

table

Поскольку 3a-1 · 5b · 7c < 3a · 5b · 7c, то число 3a-1 · 5b · 7c должно попасть в список, как и все перечисленные далее числа:

  • 3a-1 · 5 · 7c
  • 3a · 5b-1 · 7c
  • 3a · 5b · 7c-1

Другой способ — представить каждое число в следующем виде:

  • 3 · (некоторое предыдущее число из числового ряда);
  • 5 · (некоторое предыдущее число из числового ряда);
  • 7 · (некоторое предыдущее число из числового ряда).

Мы знаем, что Ak можно записать как (3, 5 или 7) · (некоторое значение из { A1, …, Ak-1}). Мы также знаем, что Ak является следующим числом в данном ряду. Поэтому Ak должно быть наименьшим «новым» числом, которое может быть получено умножением каждого значения в списке на 3, 5 или 7.

Как найти Ak? Мы можем умножить каждое число в списке на 3, 5 или 7 и найти наименьший новый результат. Но такое решение потребует O(k2) времени. Неплохо, но можно сделать и лучше.

Вместо умножения всех элементов списка на 3, 5 или 7 можно рассматривать каждое предыдущее значение как основу для расчета трёх последующих значений. Таким образом, каждое число Ai может использоваться для формирования следующих форм:

  • 3 · Ai
  • 5 · Ai
  • 7 · Ai

Эта идея поможет нам спланировать все заранее. Каждый раз, когда мы добавляем в список число Ai, мы держим значения 3Ai, 5Ai и 7Ai в «резервном» списке. Чтобы получить Ai+1, достаточно будет найти наименьшее значение во временном списке.

Наш код может быть таким:

Данный алгоритм гораздо лучше предыдущего, но все еще не идеален.

Для генерирования нового элемента Ai мы осуществляем поиск по связному списку, где каждый элемент имеет вид:

  • 3 · предыдущий элемент;
  • 5 · предыдущий элемент;
  • 7 · предыдущий элемент.

Давайте уберем избыточные расчеты. Допустим, что наш список имеет вид:

q6 = {7A1, 5A2, 7A2, 7A3, 3A4, 5A4, 7A4, 5A5, 7A5}

Когда мы ищем минимальный элемент в списке, то проверяем сначала 7A1 < min, а затем 7A5 < min. Глупо, не правда ли? Поскольку мы знаем, что A1 < A5, то достаточно выполнить проверку 7A1 < min.

Если бы мы разделили список по постоянным множителям, то должны были бы проверить только первое из произведений на 3, 5 и 7. Все последующие элементы будут больше.

Таким образом, наш список принимает вид:

  • Q36 = {3A4}
  • Q56 = {5A2, 5A4, 5A5}
  • Q76 = {7A1, 7A2, 7A3, 7A4, 7A5}

Чтобы найти минимум, достаточно проверить начало каждой очереди:

Как только мы вычислим y, нужно добавить 3y в список Q3, 5y в Q5 и 7y в Q7. Но мы хотим вставлять эти элементы, только если они отсутствуют в других списках.

Как, например, 3y может попасть в какой-нибудь другой список? Допустим, элемент y был получен из Q7, это значит, что y = 7x. Если 7x — наименьшее значение, значит, 3x уже было задействовано. А как мы действовали, когда увидели 3x? Правильно, мы вставили 7 · 3x в Q7. Обратите внимание, что 7 · 3x = 3 · 7x = 3y.

В общем виде: если мы берем элемент из Q7, он будет иметь вид 7 · suffix. Мы знаем, что 3 · suffix и 5 · suffix уже обработаны, и элемент 7 · 3 ·suffix добавлен в Q7. Единственное значение, которое мы еще не встречали — 7 · 7 · suffix, поэтому добавляем его в Q7.

Давайте рассмотрим пример, чтобы разобраться, как работает данный алгоритм. Инициализация:

Структура нашего алгоритма будет иметь вид:

  1. Инициализируем array и очереди Q3, Q5 и Q7.
  2. Вставляем 1 в array.
  3. Вставляем 1·3, 1·5, 1·7 в Q3, Q5 и Q7 соответственно.
  4. Пусть x будет минимальным элементом в Q3, Q5 и Q7.Присоединим x к magic.
  5. Если x находится в:
    • Q3 => присоединяем x·3, x·5 и x·7 к Q3, Q5 и Q7. Удаляем x из Q3.
    • Q5 => присоединяем x·5 и x·7 к Q5 и Q7. Удаляем x из Q5.
    • Q7 => присоединяем x·7 к Q7. Удаляем x из Q7.
  6. Повторяем шаги 4-6, пока k-й элемент не будет найден.

Следующий код реализует данный алгоритм:

Если вам досталась подобная задача, приложите все усилия, чтобы ее решить, потому что это действительно трудное задание. Вы можете начать с решения «в лоб» (спорно, зато не слишком сложно), а затем попытаться оптимизировать его. Или попытайтесь найти шаблон, спрятанный в числах.

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

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

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»