Выведите следующее наименьшее из 2 ^ i * 5 ^ j, где i, j> = 0

Мне недавно задали этот вопрос во время технической проверки телефона, и я не справился. Вопрос включен дословно ниже.

Создать {2^i * 5^j | i,j >= 0}отсортированную коллекцию. Непрерывно печатайте следующее наименьшее значение.

Пример: { 1, 2, 4, 5, 8, 10...}

«Следующее наименьшее» заставляет меня думать, что речь идет о минимальной куче, но я действительно не знал, куда идти, и интервьюер не оказал никакой помощи.

У кого-нибудь есть советы, как решить такую ​​проблему?

Давайте перефразируем проблему: выведите каждое число от 1 до бесконечности так, чтобы число не имело факторов, кроме 2 и 5.

Ниже приведен простой фрагмент кода C #:

for (int i = 1;;++i)
{
    int num = i;
    while(num%2 == 0) num/=2;
    while(num%5 == 0) num/=5;
    if(num == 1) Console.WriteLine(i);
}

Подход Килиана / QuestionC гораздо более производительный. Фрагмент C # с этим подходом:

var itms = new SortedSet<int>();
itms.Add(1);
while(true)
{
    int cur = itms.Min;
    itms.Remove(itms.Min);
    itms.Add(cur*2);
    itms.Add(cur*5);
    Console.WriteLine(cur);
}

SortedSet предотвращает повторные вставки.

В основном это работает, гарантируя, что следующий номер в последовательности находится в itms.

Доказательство того, что этот подход верен:
описанный алгоритм гарантирует, что после любого числа, выводимого в форму 2^i*5^j, набор теперь содержит 2^(i+1)*5^jи 2^i*5^(j+1). Предположим, что следующий номер в последовательности 2^p*5^q. Должно существовать ранее выведенное число вида 2^(p-1)*5^(q)или 2^p*5^(q-1)(или обоих, если ни p, ни q не равны 0). Если нет, то 2^p*5^qэто не следующий номер, так как 2^(p-1)*5^(q)и 2^p*5^(q-1)оба меньше.

Второй фрагмент использует O(n)память (где n - это число чисел, которые были выведены), поскольку O(i+j) = O(n)(поскольку i и j оба меньше, чем n), и найдет n чисел во O(n log n)времени. Первый фрагмент находит числа в экспоненциальном времени.

Это достаточно распространенный вопрос интервью, поэтому полезно знать ответ. Вот соответствующая запись в моей личной кроватке:

• чтобы сгенерировать числа в форме 3 ^a 5 ^b 7 ^c по порядку , начните с 1, добавьте всех трех возможных преемников (3, 5, 7) во вспомогательную структуру, затем добавьте наименьшее число из этого числа в свой список.

Другими словами, вам нужен двухэтапный подход с дополнительным отсортированным буфером для эффективного решения этой проблемы. (Хорошее длинное описание в « Взломе кодирования » Гейл Макдауэлл.

Вот ответ, который работает с постоянной памятью, за счет процессора. Это не очень хороший ответ в контексте исходного вопроса (т.е. ответ во время интервью). Но если интервью длится 24 часа, то это не так уж плохо. ;)

Идея состоит в том, что если у меня есть n, который является действительным ответом, то следующий в последовательности будет n умножить на некоторую степень двух, деленную на некоторую степень 5. Или иначе n раз степень 5, деленную на сила двух. При условии, что он делится равномерно. (... или делитель может быть 1;) в этом случае вы просто умножаете на 2 или 5)

Например, чтобы перейти от 625 к 640, умножьте на 5 ** 4/2 ** 7. Или, в более общем случае, умножьте на некоторое значение 2 ** m * 5 ** nдля некоторого m, n, где один положительный, а другой отрицательный или ноль, и множитель делит число равномерно.

Теперь самое сложное - найти множитель. Но мы знаем, что а) делитель должен делить число равномерно, б) множитель должен быть больше единицы (числа продолжают расти), и в) если мы выберем наименьший множитель больше 1 (то есть 1 <f <все остальные f ), то это будет нашим следующим шагом. Шаг после этого будет самым низким шагом.

Неприятная часть находит значение m, n. Есть только log (n) возможности, потому что есть только 2 или 5, которые нужно сдать, но мне пришлось добавить коэффициент от -1 до +1, как неаккуратный способ борьбы с округлением. Таким образом, нам нужно только пройти через O (log (n)) каждый шаг. Так что это O (n log (n)) в целом.

Хорошей новостью является то, что, поскольку оно принимает значение и находит следующее значение, вы можете начать в любом месте последовательности. Поэтому, если вам нужен следующий после 1 миллиарда, он может просто найти его, перебирая 2/5 или 5/2 и выбирая наименьший множитель больше 1.

(Python)

MAX = 30
F = - math.log(2) / math.log(5)

def val(i, j):
    return 2 ** i * 5 ** j

def best(i, j):
    f = 100
    m = 0
    n = 0
    max_i = (int)(math.log(val(i, j)) / math.log(2) + 1) if i + j else 1
    #print((val(i, j), max_i, x))
    for mm in range(-i, max_i + 1):
        for rr in {-1, 0, 1}:
            nn = (int)(mm * F + rr)
            if nn < -j: continue
            ff = val(mm, nn)
            #print('  ' + str((ff, mm, nn, rr)))
            if ff > 1 and ff < f:
                f = ff
                m = mm
                n = nn
    return m, n

def detSeq():

    i = 0
    j = 0
    got = [val(i, j)]

    while len(got) < MAX:
        m, n = best(i, j)

        i += m
        j += n
        got.append(val(i, j))

        #print('* ' + str((val(i, j), m, n)))
        #print('- ' + str((v, i, j)))

    return got

Я проверил первые 10000 чисел, которые это генерирует, против первых 10000, сгенерированных решением с отсортированным списком, и это работает, по крайней мере, так далеко.

Кстати, следующий после триллиона, кажется, 1 024 000 000 000.

...

Гектометр Я могу получить производительность O (n) - O (1) на значение (!) - и использование памяти O (log n), рассматривая best()как справочную таблицу, которую я постепенно расширяю. Прямо сейчас он экономит память путем итерации каждый раз, но выполняет много избыточных вычислений. Держа эти промежуточные значения - и список минимальных значений - я могу избежать дублирования работы и значительно ускорить ее. Тем не менее, список промежуточных значений будет расти с ростом n, следовательно, O (log n) памяти.

Брайан был абсолютно прав - мой другой ответ был слишком сложным. Вот более простой и быстрый способ сделать это.

Представьте себе Квадрант I евклидовой плоскости, ограниченный целыми числами. Назовите одну ось по оси i, а другую ось по оси j.

Очевидно, что точки рядом с началом координат будут выбраны раньше точек, удаленных от начала координат. Также обратите внимание, что активная область отойдет от оси i, прежде чем она отойдет от оси j.

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

Собрав их вместе, вы можете представить себе «границу» или «передний край», который начинается вокруг начала координат, и они распространяются вверх и вправо, распространяясь вдоль оси i дальше, чем на оси j.

На самом деле, мы можем придумать что-то большее: для любой заданной i-величины будет самое большее одна точка на границе / крае. (Вы должны увеличивать i более чем в 2 раза, чтобы равняться приращению j.) Таким образом, мы можем представить границу в виде списка, содержащего один элемент для каждой координаты i, который изменяется только в зависимости от координаты j и значения функции.

Каждый проход мы выбираем минимальный элемент на переднем крае, а затем перемещаем его в направлении j один раз. Если нам случается поднять последний элемент, мы добавляем новый последний дополнительный элемент с увеличенным значением i и значением j, равным 0.

using System;
using System.Collections.Generic;
using System.Text;

namespace TwosFives
{
    class LatticePoint : IComparable<LatticePoint>
    {
      public int i;
      public int j;
      public double value;
      public LatticePoint(int ii, int jj, double vvalue)
      {
          i = ii;
          j = jj;
          value = vvalue;
      }
      public int CompareTo(LatticePoint rhs)
      {
          return value.CompareTo(rhs.value);
      }
    }


    class Program
    {
        static void Main(string[] args)
        {
            LatticePoint startPoint = new LatticePoint(0, 0, 1);

            var leadingEdge = new List<LatticePoint> { startPoint } ;

            while (true)
            {
                LatticePoint min = leadingEdge.Min();
                Console.WriteLine(min.value);
                if (min.j + 1 == leadingEdge.Count)
                {
                    leadingEdge.Add(new LatticePoint(0, min.j + 1, min.value * 2));
                }
                min.i++;
                min.value *= 5;
            }
        }
    }
}

Пробел: O (n) в количестве напечатанных элементов.

Скорость: O (1) вставки, но это не каждый раз. (Иногда дольше, когда List<>должен расти, но все еще O (1) амортизируется). Большое сокращение времени - это поиск минимума O (n) в количестве напечатанных элементов.

Решение, основанное на множестве, вероятно, было тем, что искал ваш интервьюер, однако, к сожалению, оно имеет следствие наличия O(n)памяти и O(n lg n)общего времени для nэлементов последовательности .

Немного математики помогает нам найти решение в O(1)пространстве и O(n sqrt(n))времени. Обратите внимание на это 2^i * 5^j = 2^(i + j lg 5). Нахождение первых nэлементов {i,j > 0 | 2^(i + j lg 5)}сводится к нахождению первых nэлементов, {i,j > 0 | i + j lg 5}потому что функция (x -> 2^x)строго монотонно возрастает, поэтому единственный путь для некоторых a,bэто 2^a < 2^bесли a < b.

Теперь нам просто нужен алгоритм, чтобы найти последовательность i + j lg 5, где i,jнатуральные числа. Другими словами, учитывая наше текущее значение того i, j, что минимизирует следующий ход (т. Е. Дает нам следующее число в последовательности), это некоторое увеличение одного из значений (скажем j += 1) наряду с уменьшением другого ( i -= 2). Единственное, что нас ограничивает, так это i,j > 0.

Есть только два случая, чтобы рассмотреть - iувеличивается или jувеличивается. Один из них должен увеличиваться, так как наша последовательность увеличивается, и оба не увеличиваются, потому что в противном случае мы пропускаем термин, в котором у нас есть только один термин i,jувеличение. Таким образом, один увеличивается, а другой остается неизменным или уменьшается. Выраженный в C ++ 11, весь алгоритм и его сравнение с заданным решением доступны здесь .

Это обеспечивает постоянную память, поскольку в методе выделяется только постоянное количество объектов, кроме выходного массива (см. Ссылку). Метод достигает логарифмического времени на каждой итерации, поскольку для любой заданной точки (i,j)он пересекает лучшую пару (a, b), что (i + a, j + b)является наименьшим увеличением значения i + j lg 5. Это обход O(i + j):

Attempt to increase i:
++i
current difference in value CD = 1
while (j > 0)
  --j
  mark difference in value for
     current (i,j) as CD -= lg 5
  while (CD < 0) // Have to increase the sequence
    ++i          // This while will end in three loops at most.
    CD += 1
find minimum among each marked difference ((i,j) -> CD)

Attempt to increase j:
++j
current difference in value CD = lg 5
while (j > 0)
  --i
  mark difference in value for
     current (i,j) as CD -= 1
  while (CD < 0) // have to increase the sequence
    ++j          // This while will end in one loop at most.
    CD += lg 5
find minimum among each marked difference ((i,j) -> CD)

Каждая итерация пытается обновить i, а затем jидет с меньшим обновлением из двух.

Так как iи jсамое большее O(sqrt(n)), у нас есть общее O(n sqrt(n))время. iи jрасти со скоростью квадрата с тех nпор для любых максимальных значений, imaxи jmaxсуществуют O(i j)уникальные пары, из которых можно составить нашу последовательность, если наша последовательность является nчленами, iи jрасти в некотором постоянном множителе друг друга (поскольку показатель степени состоит из линейного сочетание для двух), мы знаем, что iи jесть O(sqrt(n)).

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