Хитрый вопрос об интервью Google

169

Мой друг берет интервью на работу. Один из вопросов на собеседовании заставил меня задуматься, просто хотелось получить обратную связь.

Есть 2 неотрицательных целых числа: i и j. Учитывая следующее уравнение, найдите (оптимальное) решение для итерации по i и j таким образом, чтобы выходные данные были отсортированы.

2^i * 5^j

Итак, первые несколько раундов будут выглядеть так:

2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25

Как ни старайся, я не вижу картины. Твои мысли?

Крис Эберле
источник
63
Оптимальный алгоритм с точки зрения времени программиста - генерировать с двумя вложенными циклами, а затем сортировать. Почему они задают такие вопросы?
Том Зыч
21
Вы можете определить точки перехода, посмотрев, какое число больше. 2^2 < 5но 2^3 > 5так в этот момент вы увеличиваете J. Я думаю, что вы можете произвести вывод в O (n), а не O (nlgn). @ tom-zynch два вложенных цикла - это O (n ^ 2). Этот вопрос очень актуален
Михаил
1
Выход только один, поэтому оптимальным решением является O (n). Прочитайте мое решение ниже
Михаил
3
Подобный вопрос уже был адресован ранее: stackoverflow.com/questions/4600048/nth-ugly-number .
1
... и ОП, вероятно, должен уже выбрать ответ. В конце концов, у него уже есть много хороших.
abeln

Ответы:

123

Дейкстра получает красноречивое решение в «Дисциплине программирования». Он приписывает проблему Хэммингу. Вот моя реализация решения Дейкстры.

int main()
{
    const int n = 20;       // Generate the first n numbers

    std::vector<int> v(n);
    v[0] = 1;

    int i2 = 0;             // Index for 2
    int i5 = 0;             // Index for 5

    int x2 = 2 * v[i2];     // Next two candidates
    int x5 = 5 * v[i5];

    for (int i = 1; i != n; ++i)
    {
        int m = std::min(x2, x5);
        std::cout << m << " ";
        v[i] = m;

        if (x2 == m)
        {
            ++i2;
            x2 = 2 * v[i2];
        }
        if (x5 == m)
        {
            ++i5;
            x5 = 5 * v[i5];
        }
    }

    std::cout << std::endl;
    return 0;
}
user515430
источник
18
Соответствующая ссылка: en.wikipedia.org/wiki/Regular_number#Algorithms . Кстати, я не думаю, что это очень хороший вопрос для интервью. Вот (рукописная статья) Дейкстры, где он предоставляет и доказывает алгоритм решения этой проблемы: cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF
Элиан
Когда цель состоит в том, чтобы «перебрать i и j», вам потребуется меньше места для хранения, достаточно FIFO. Смотрите мое решение Python.
GaBorgulya
7
Когда целью является «перебрать i и j», это не та же проблема.
Мм
Это действительно хорошая реализация, использующая минимум памяти. Это линейная память, даже если вы хотите только одно число.
Томас Але
1
@ThomasAhle Не знаю, видели ли вы это, но в конце у него есть код, способный вычислять n-е число изолированно. Как например, миллиардное число .
Уилл Несс
47

вот более изощренный способ сделать это (более изощренный, чем мой предыдущий ответ, то есть):

Представьте, что числа помещены в матрицу:

     0    1    2    3    4    5   -- this is i
----------------------------------------------
0|   1    2    4    8   16   32
1|   5   10   20   40   80  160
2|  25   50  100  200  400  800
3| 125  250  500 1000 2000 ...
4| 625 1250 2500 5000 ...
j on the vertical

что вам нужно сделать, это «пройтись» по этой матрице, начиная с (0,0). Вы также должны отслеживать, каковы ваши возможные следующие шаги. Когда вы начинаете (0,0)вас есть только два варианта: либо (0,1)или (1,0): так как значение (0,1)меньше, вы выбираете , что. затем сделайте то же самое для вашего следующего выбора (0,2)или (1,0). До сих пор, у вас есть следующий список: 1, 2, 4. Ваш следующий шаг - (1,0)значение там меньше, чем (0,3). Тем не менее, теперь у вас есть три варианта для вашего следующего хода: либо (0,3), либо (1,1), либо (2,0).

Вам не нужна матрица, чтобы получить список, но вам нужно отслеживать все ваши выборы (т.е. когда вы достигнете 125+, у вас будет 4 варианта).

влад
источник
Я проголосовал за это, потому что я думал в том же духе, но в общем случае, это не было бы что-то вроде O (i ^ 2 * j)? Вы должны проверить несколько номеров для каждого номера, который вы выводите.
Том Зыч
1
@ То есть вам нужно проверить более одного числа, но это не так уж и плохо: когда вы выводите числа от 125 до 625, вам нужно посмотреть на 4 значения. между 625 и 3025 вы смотрите на 5 значений. так на самом деле, это jпроверка для каждого 1 выхода
влад
+1: Объединить с этим вопросом: stackoverflow.com/questions/5000836/search-algorithm и похоже, что у нас есть решение O (n).
@ Морон, черт возьми, я не хочу платить 25 долларов за этот алгоритм, но он выглядит интересно.
влад
1
фактически, j ~ n^0.5для n-го значения в последовательности, поскольку nзначения заполняют область на i x jплоскости. Так что этот алгоритм - O(n^1.5)время, с O(n^0.5)пространством. Но существует линейный алгоритм времени с той же пространственной сложностью n^0.5, и алгоритм мини-кучи из ответа ниже - O(n*log(n))время с тем же n^0.5пространством.
Уилл Несс
25

Используйте Мин-кучу.

Ставь 1.

экстракт-Мин. Скажем, вы получили х.

Нажмите 2x и 5x в кучу.

Повторение.

Вместо сохранения x = 2 ^ i * 5 ^ j вы можете сохранить (i, j) и использовать пользовательскую функцию сравнения.


источник
1
Куча даст lg n времени на свои операции, что увеличивает сложность до n lg n.
CorsiKa
@glow: Да, я пока не вижу ни одного O (n) решения, опубликованного :-)
@abel: Этот комментарий старый :-) Похоже, у него тоже будут проблемы с (1,1) до (4,0). Но просмотр ее как матрицы Юнга (см. Ответ Влада) на самом деле допускает O (n) временной алгоритм.
@ Морон: Я не думаю, что с этим решением что-то не так. Конечно, нет ничего плохого в первых 30 элементах, которые я только что проверил (это охватывало случай (1,1) -> (4,0)).
abeln
@abel: Да, на самом деле не пытался запустить его :-) Возможно, есть и легкое доказательство его правильности. FWIW, у него уже есть мой +1.
13

Решение на основе FIFO требует меньшего объема памяти. Код Python

F = [[1, 0, 0]]             # FIFO [value, i, j]
i2 = -1; n2 = n5 = None     # indices, nexts
for i in range(1000):       # print the first 1000
    last = F[-1][:]
    print "%3d. %21d = 2^%d * 5^%d" % tuple([i] + last)
    if n2 <= last: i2 += 1; n2 = F[i2][:]; n2[0] *= 2; n2[1] += 1
    if n5 <= last: i2 -= 1; n5 = F.pop(0); n5[0] *= 5; n5[2] += 1
    F.append(min(n2, n5))

вывод:

  0.                     1 = 2^0 * 5^0
  1.                     2 = 2^1 * 5^0
  2.                     4 = 2^2 * 5^0
 ...
998. 100000000000000000000 = 2^20 * 5^20
999. 102400000000000000000 = 2^27 * 5^17
GaBorgulya
источник
6

Это очень легко сделать O(n)на функциональных языках. Список lиз 2^i*5^jномеров может быть просто определен как 1и то 2*lи 5*lобъединен. Вот как это выглядит в Haskell:

merge :: [Integer] -> [Integer] -> [Integer]
merge (a:as) (b:bs)   
  | a < b   = a : (merge as (b:bs))
  | a == b  = a : (merge as bs)
  | b > a   = b : (merge (a:as) bs)

xs :: [Integer]
xs = 1 : merge (map(2*)xs) (map(5*)xs)

mergeФункция дает новое значение в постоянная время. Так и делает, mapа значит, и делает l.

Томас Але
источник
Я думаю, что 'k' не определено
Ither
2
давайте просто вызовем эту функцию «слияния» union, поскольку она удаляет дубликаты. mergeкак часть mergesort, должен сохранить дубликаты, поступающие из обеих его входных последовательностей. Смотрите Data.List.Orderedпакет для связанных вещей.
Уилл Несс
1
+1 за Data.List.Ordered.union. Это делает его одной строкой:xs = 1 : union (map (2*) xs) (map (5*) xs)
Фоб
@GaBorgulya Да, это включает в себя пять раз список, [1, 2, 4, 5,...]поэтому он включает 5*4.
Томас Але
1
@Phob Да, это Data.List.Ordered.unionфункция. Не путать с Data.List.union.
Томас Але
5

Вы должны отслеживать их отдельные показатели, и каковы их суммы

Итак, начните с того, что f(0,0) --> 1 вам нужно увеличить одно из них:

f(1,0) = 2
f(0,1) = 5

поэтому мы знаем, что следующим является 2 - мы также знаем, что можем увеличивать показатель i до тех пор, пока сумма не превысит 5.

Вы продолжаете идти вперед и назад, пока не достигнете нужного количества раундов.

corsiKa
источник
Да, это так. Вы делаете одну O (1) операцию для каждого раунда. Иногда вы делаете раунд рано, но когда вы добираетесь до этого раунда, вам не нужно делать это там, так что это работает само собой.
CorsiKa
19
Как вы переходите от (1,1) к (4,0)? Пожалуйста, уточните, каков ваш алгоритм.
Проблема в том, что у вас не просто две дополнительные возможности - например, вы не закончили f(*,2)только потому, что нашли это f(a1,b+1)>f(a2,b). Инкрементальный подход в конечном итоге будет генерировать неограниченное количество пар, соседствующих с областью, которую вы уже вывели.
Грядущая буря
@ user515430 предоставил реализацию, которая была больше, чем я мог сделать на обеденном перерыве, но я пытался достичь этого.
CorsiKa
4

Используя динамическое программирование, вы можете сделать это в O (n). Основная истина заключается в том, что никакие значения i и j не могут дать нам 0, и чтобы получить 1, оба значения должны быть 0;

TwoCount[1] = 0
FiveCount[1] = 0

// function returns two values i, and j
FindIJ(x) {
    if (TwoCount[x / 2]) {
        i = TwoCount[x / 2] + 1
        j = FiveCount[x / 2]
    }
    else if (FiveCount[x / 5]) {
        i = TwoCount[x / 2]
        j = FiveCount[x / 5] + 1
    }
}

Всякий раз, когда вы вызываете эту функцию, проверьте, установлены ли i и j, если они не равны NULL, затем заполните TwoCountиFiveCount


C ++ ответ. Извините за плохой стиль кодирования, но я тороплюсь :(

#include <cstdlib>
#include <iostream>
#include <vector>

int * TwoCount;
int * FiveCount;

using namespace std;

void FindIJ(int x, int &i, int &j) {
        if (x % 2 == 0 && TwoCount[x / 2] > -1) {
                cout << "There's a solution for " << (x/2) << endl;
                i = TwoCount[x / 2] + 1;
                j = FiveCount[x / 2];
        } else if (x % 5 == 0 && TwoCount[x / 5] > -1) {
                cout << "There's a solution for " << (x/5) << endl;
                i = TwoCount[x / 5];
                j = FiveCount[x / 5] + 1;
        }    
}

int main() {
        TwoCount = new int[200];
        FiveCount = new int[200];

        for (int i = 0; i < 200; ++i) {
                TwoCount[i] = -1;
                FiveCount[i] = -1;
        }

        TwoCount[1] = 0;
        FiveCount[1] = 0;

        for (int output = 2; output < 100; output++) {
                int i = -1;
                int j = -1;
                FindIJ(output, i, j);
                if (i > -1 && j > -1) {
                        cout << "2^" << i << " * " << "5^" 
                                     << j << " = " << output << endl;
                        TwoCount[output] = i;
                        FiveCount[output] = j;
                }
        }    
}

Очевидно, что вы можете использовать структуры данных, отличные от массива, для динамического увеличения хранилища и т. Д. Это всего лишь эскиз, чтобы доказать, что он работает.

Михаил
источник
4
Это выглядит как интересный ответ, но я не вижу, как это действительно работает. Не могли бы вы добавить больше деталей?
Дэвид Брунел
Изучив это сам, я действительно не понимаю, как это работает. Предполагая целочисленное деление, он даст тот же результат для 3, что и для 2. Более того, если условия являются тестами на ненулевое значение, оно никогда не будет работать, поскольку нет ненулевых записей.
Дэвид Торнли
Выложил версию C ++ для всех вас, кто скажет. @David Ваши комментарии верны, но мой оригинальный код был псевдокодом, и я думал в терминах сценариев, поэтому не целочисленное деление и различие между нулевым вводом и вводом значения 0
Михаил
этот код перечисляет все натуральные числа, поэтому, согласно комментарию @ThomasAhle к ответу «Затерянный в Алабаме», приведенному ниже, требуется O(exp(sqrt(n)))получить nчисла последовательности. Линейный алгоритм существует, например, как указано ThomasAhle.
Уилл Несс
1
Ты прав. В моем понимании O(n)подразумевается nпоследнее значение, а не количество напечатанных элементов, что не правильно. Я не знаю, как работают функциональные языки или как работает слияние в постоянное время, но его ответ получил мое одобрение
Михаил
2

Почему бы не попробовать посмотреть на это с другой стороны. Используйте счетчик, чтобы проверить возможные ответы по оригинальной формуле. Извините за псевдокод.

for x = 1 to n
{
  i=j=0
  y=x
  while ( y > 1 )
  {
    z=y
    if y divisible by 2 then increment i and divide y by 2
    if y divisible by 5 then increment j and divide y by 5

    if y=1 then print i,j & x  // done calculating for this x

    if z=y then exit while loop  // didn't divide anything this loop and this x is no good 
  }
}
Затерянный в Алабаме
источник
Это происходит примерно O(4^sqrt(n))потому, что nthномер последовательности примерно такого же размера.
Томас Але
2

Это соответствующая запись в OEIS.

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

1 2 4 5

а затем, начиная со второго слагаемого, умножая на 4 и 5, чтобы получить следующие два

1 2 4 5 8 10

1 2 4 5 8 10 16 20

1 2 4 5 8 10 16 20 25

и так далее...

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

abeln
источник
2
Неправильно :( [1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 625 ] Однако 500 <512 = 2 ^ 9 <625.
ГаБоргуля
1
@NateKerkhofs, 512 сгенерировано, но оно вышло из строя, так как 512 меньше уже сгенерированного 625; алгоритму потребуется дополнительная логика для упорядочения выходных данных. Таким образом, алгоритм не такой простой, как предложенный, и совсем не тот же алгоритм.
GordonBGood
1

Вы знаете, что log_2 (5) = 2,32. Из этого отметим, что 2 ^ 2 <5 и 2 ^ 3> 5.

Теперь посмотрите матрицу возможных ответов:

j/i  0   1   2   3   4   5
 0   1   2   4   8  16  32
 1   5  10  20  40  80 160 
 2  25  50 100 200 400 800
 3 125 250 500 ...

Теперь, для этого примера, выберите номера по порядку. Там порядок будет:

j/i  0   1   2   3   4   5
 0   1   2   3   5   7  10
 1   4   6   8  11  14  18
 2   9  12  15  19  23  27
 3  16  20  24...

Обратите внимание, что каждая строка начинается на 2 столбца позади строки, начинающей ее. Например, i = 0 j = 1 наступает сразу после i = 2 j = 0.

Следовательно, алгоритм, который мы можем вывести из этого шаблона, (предположим, j> i):

int i = 2;
int j = 5;
int k;
int m;

int space = (int)(log((float)j)/log((float)i));
for(k = 0; k < space*10; k++)
{
    for(m = 0; m < 10; m++)
    {
        int newi = k-space*m;
        if(newi < 0)
            break;
        else if(newi > 10)
            continue;
        int result = pow((float)i,newi) * pow((float)j,m);
        printf("%d^%d * %d^%d = %d\n", i, newi, j, m, result);
    }
}   

ПРИМЕЧАНИЕ: код здесь ограничивает значения показателей степени i и j, чтобы быть меньше 10. Вы можете легко расширить этот алгоритм, чтобы вписаться в любые другие произвольные границы.

ПРИМЕЧАНИЕ. Время выполнения этого алгоритма составляет O (n) для первых n ответов.

ПРИМЕЧАНИЕ. Пространственная сложность этого алгоритма равна O (1).

KLee1
источник
Вы написали "каждая строка начинается с 2 столбцов позади строки, начинающей ее". Однако 2 ^ 9 = 512 и 5 ^ 4 = 625, так что это не так для 4-й строки.
ГаБоргуля
@ user678105 Вы правы. Этот код не работает. Извините все. Этот код не работает из-за округления журнала и моего предположения, что это не имеет значения.
KLee1
1
Вот как это исправить. На плоскости (x, y), полной точек с интегральными коэффициентами, проведите линию от (0,1) до (log2 (5), 0). (0,0) находится в верхнем левом углу. Ось X направлена ​​вправо, ось Y направлена ​​вниз. Теперь нарисуйте линию от (0,0) исходной точки, которая перпендикулярна 1-й линии. Теперь проведите первую линию вдоль второй, дальше и дальше от начала координат и соберите точки целочисленных координат, когда они пересекаются. Для {2,3,5} -генерированной последовательности это будет плоскость, движущаяся поперек в (i, j, k) пространстве. Если вы можете перевести эту идею в код, дайте мне крик. :)
Уилл Несс
1

Моя реализация основана на следующих идеях:

  • Используйте две очереди Q2 и Q5, обе с инициализацией 1. Мы будем держать обе очереди в отсортированном порядке.
  • На каждом шаге удаляйте наименьший элемент числа MIN из Q2 или Q5 и печатайте его. Если оба Q2 и Q5 имеют одинаковый элемент - удалите оба. Распечатайте этот номер. По сути, это объединение двух отсортированных массивов - на каждом шаге выбирайте наименьший элемент и переходите вперед.
  • Поставьте в очередь значения от MIN * 2 до Q2 и от MIN * 5 до Q5. Это изменение не нарушает сортируемый инвариант Q2 / Q5, потому что MIN выше, чем предыдущий номер MIN.

Пример:

Start with 1 and 1 (to handle i=0;j=0 case):
  Q2: 1
  Q5: 1
Dequeue 1, print it and enqueue 1*2 and 1*5:
  Q2: 2
  Q5: 5
Pick 2 and add 2*2 and 2*5:
  Q2: 4
  Q5: 5 10
Pick 4 and add 4*2 and 4*5:
  Q2: 8
  Q5: 5 10 20
....

Код на Java:

public void printNumbers(int n) {
    Queue<Integer> q2 = new LinkedList<Integer>();
    Queue<Integer> q5 = new LinkedList<Integer>();
    q2.add(1);
    q5.add(1);
    for (int i = 0; i < n; i++) {
        int a = q2.peek();
        int b = q5.peek();
        int min = Math.min(a, b);
        System.out.println(min);
        if (min == a) {
            q2.remove();
        }
        if (min == b) {
            q5.remove();
        }
        q2.add(min * 2);
        q5.add(min * 5);
    }
}
ejboy
источник
0

рассчитать результаты и поместить их в отсортированный список вместе со значениями iиj

влад
источник
Это, вероятно, даст вам дыры в более позднем конце вашей последовательности. Например, у вас будет, 2^n*5^nно не 2^(n+1)*5^(n-1)меньше.
Томас Але
@ Томас Я не уверен, что следую вашей логике здесь. Если вы рассчитываете одно, почему бы вам не рассчитать и другое?
влад
2
@vlad Вы должны иметь ограничение на ваш i«s и j» s, не так ли? В противном случае вы никогда не доберетесь до состояния сортировки и, следовательно, никогда не вернете ни одного значения. Но для любого ограничения, которое nвы выберете, ваш список будет ошибочным.
Томас Але
@ Томас, твой аргумент все еще не имеет смысла. ОП никогда не указывал конец своему списку результатов. Если он это сделает, вы можете найти максимум iи j.
влад
1
@vlad Когда я читаю ваш ответ, вы сначала рассчитываете "результаты" / 2^i*5^j значения, а затем сортируете их. Если у вас нет ограниченного числа «результатов», как вы попадете на этап сортировки?
Томас Але
0

Алгоритм, реализованный пользователем 515430 Эдсгером Дейкстрой (http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF), вероятно, работает настолько быстро, насколько вы можете этого добиться. Я звоню на каждый номер, который является формой 2^i * 5^j«специального номера». Теперь ответ vlads будет, O(i*j)но с двойным алгоритмом, один для генерации специальных чисел O(i*j)и один для их сортировки (согласно связанной статье также O(i*j).

Но давайте проверим алгоритм Дейкстры (см. Ниже). В этом случае nколичество специальных чисел, которые мы генерируем, равно i*j. Мы делаем цикл один раз, 1 -> nи в каждом цикле мы выполняем постоянное действие. Так что этот алгоритм тоже O(i*j). И с довольно яркой быстрой константой тоже.

Моя реализация в C ++ с GMP (оболочка C ++) и зависимость от boost::lexical_cast , хотя ее легко удалить (я ленив, а кто не использует Boost?). Составлено с g++ -O3 test.cpp -lgmpxx -o test. На Q6600 Ubuntu 10.10 time ./test 1000000выдает 1145ms.

#include <iostream>
#include <boost/lexical_cast.hpp>
#include <gmpxx.h>

int main(int argc, char *argv[]) {
    mpz_class m, x2, x5, *array, r;
    long n, i, i2, i5;

    if (argc < 2) return 1;

    n = boost::lexical_cast<long>(argv[1]);

    array = new mpz_class[n];
    array[0] = 1;

    x2 = 2;
    x5 = 5;
    i2 = i5 = 0;

    for (i = 1; i != n; ++i) {
        m = std::min(x2, x5);

        array[i] = m;

        if (x2 == m) {
            ++i2;
            x2 = 2 * array[i2];
        }

        if (x5 == m) {
            ++i5;
            x5 = 5 * array[i5];
        }
    }

    delete [] array;
    std::cout << m << std::endl;

    return 0;
}
orlp
источник
0

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

Так что для i = 7 вы путешествуете так:

7, 0 -> 5, 1 -> 3, 2 -> 1, 3

И для я = 8:

8, 0 -> 6, 1 -> 4, 2 -> 2, 3 -> 0, 4

Здесь это происходит в Java до i = 9. Он печатает положение матрицы (i, j) и значение.

for(int k = 0; k < 10; k++) {

    int j = 0;

    for(int i = k; i >= 0; i -= 2) {

        int value = (int)(Math.pow(2, i) * Math.pow(5, j));
        System.out.println(i + ", " + j + " -> " + value);
        j++;
    }
}
уютное местечко
источник
0

Моя интуиция :

Если я беру начальное значение как 1, где i = 0, j = 0, то я могу создать следующие числа как (2 ^ 1) (5 ^ 0), (2 ^ 2) (5 ^ 0), (2 ^ 0) * (5 ^ 1), ... т.е. 2,4,5 ..

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

  • х * 2
  • х * 4
  • х * 5

Пояснение :

Since new numbers can only be the product with 2 or 5.
But 4 (pow(2,2)) is smaller than 5, and also we have to generate 
Numbers in sorted order.Therefore we will consider next numbers
be multiplied with 2,4,5.
Why we have taken x*4 ? Reason is to pace up i, such that it should not 
be greater than pace of j(which is 5 to power). It means I will 
multiply my number by 2, then by 4(since 4 < 5), and then by 5 
to get the next three numbers in sorted order.

Тестовый забег

We need to take an Array-list of Integers, let say Arr.

Also put our elements in Array List<Integers> Arr.
Initially it contains Arr : [1]
  • Давайте начнем с х = 1.

    Следующие три числа: 1 * 2, 1 * 4, 1 * 5 [2,4,5]; ARR [1,2,4,5]

  • Теперь х = 2

    Следующие три числа: [4,8,10] {Так как 4 уже произошло, мы его проигнорируем} [8,10]; ARR [1,2,4,5,8,10]

  • Теперь х = 4

    Следующие три числа [8,16,20] {8 уже произошло, игнорируйте его} [16,20] Arr [1,2,4,5,8,10,16,20]

  • х = 5

    Следующие три числа [10,20,25] {10,20} уже так [25] добавляется Arr [1,2,4,5,8,10,16,20,25]

Условие прекращения

 Terminating condition when Arr last number becomes greater 
 than (5^m1 * 2^m2), where m1,m2 are given by user.

Анализ

 Time Complexity : O(K) : where k is numbers possible between i,j=0 to 
 i=m1,j=m2.
 Space Complexity : O(K)
bharatj
источник
0

Просто было интересно, чего ожидать на следующей неделе и нашли этот вопрос.

Я думаю, идея в том, что 2 ^ i увеличивается не такими большими шагами, как 5 ^ j. Так что увеличивайте i, пока следующий j-шаг не будет больше.

Пример на C ++ (Qt не обязателен):

QFile f("out.txt"); //use output method of your choice here
f.open(QIODevice::WriteOnly);
QTextStream ts(&f);

int i=0;
int res=0;
for( int j=0; j<10; ++j )
{
    int powI = std::pow(2.0,i );
    int powJ = std::pow(5.0,j );
    while ( powI <= powJ  ) 
    {
        res = powI * powJ;
        if ( res<0 ) 
            break; //integer range overflow

        ts<<i<<"\t"<<j<<"\t"<<res<<"\n";
        ++i;
        powI = std::pow(2.0,i );

    }
}

Выход:

i   j   2^i * 5^j
0   0   1
1   1   10
2   1   20
3   2   200
4   2   400
5   3   4000
6   3   8000
7   4   80000
8   4   160000
9   4   320000
10  5   3200000
11  5   6400000
12  6   64000000
13  6   128000000
14  7   1280000000
Валентин Хайниц
источник
Это решение пропускает некоторые комбинации. Например, он не рассматривает случай, когда i = 1, j = 2, любой случай, когда i = 1 и j> 1 по этому вопросу.
Федерико
@ Федерико: Вы правы! Не удивительно, почему я дважды провалил google-интервью с 6-летним интервалом, но почти с
такими
0

Вот мое решение

#include <stdio.h>
#include <math.h>
#define N_VALUE 5
#define M_VALUE  5

int n_val_at_m_level[M_VALUE];

int print_lower_level_val(long double val_of_higher_level, int m_level)
{
int  n;
long double my_val;


for( n = n_val_at_m_level[m_level]; n <= N_VALUE; n++) {
    my_val =  powl(2,n) * powl(5,m_level);
    if(m_level != M_VALUE && my_val > val_of_higher_level) {
        n_val_at_m_level[m_level] = n;
        return 0;
    }
    if( m_level != 0) {
        print_lower_level_val(my_val, m_level - 1);
    }
    if(my_val < val_of_higher_level || m_level == M_VALUE) {
        printf("    %Lf n=%d m = %d\n", my_val, n, m_level);
    } else {
        n_val_at_m_level[m_level] = n;
        return 0;
    }
 }
 n_val_at_m_level[m_level] = n;
 return 0;
 }


 main()
 {
    print_lower_level_val(0, M_VALUE); /* to sort 2^n * 5^m */
 }

Результат:

1.000000 n = 0 m = 0
2.000000 n = 1 m = 0
4.000000 n = 2 m = 0
5.000000 n = 0 m = 1
8.000000 n = 3 m = 0
10.000000 n = 1 m = 1
16.000000 n = 4 m = 0
20.000000 n = 2 m = 1
25.000000 n = 0 m = 2
32.000000 n = 5 m = 0
40.000000 n = 3 m = 1
50.000000 n = 1 m = 2
80.000000 n = 4 m = 1
100.000000 n = 2 m = 2
125.000000 n = 0 m = 3
160.000000 n = 5 m = 1
200.000000 n = 3 m = 2
250.000000 n = 1 m = 3
400.000000 n = 4 m = 2
500.000000 n = 2 m = 3
625.000000 n = 0 m = 4
800.000000 n = 5 m = 2
1000.000000 n = 3 m = 3
1250.000000 n = 1 m = 4
2000.000000 n = 4 m = 3
2500.000000 n = 2 m = 4
3125.000000 n = 0 m = 5
4000.000000 n = 5 m = 3
5000.000000 n = 3 m = 4
6250.000000 n = 1 m = 5
10000.000000 n = 4 m = 4
12500.000000 n = 2 m = 5
20000.000000 n = 5 m = 4
25000.000000 n = 3 m = 5
50000.000000 n = 4 m = 5
100000.000000 n = 5 m = 5
dhanasubbu
источник
0

Я знаю, что, скорее всего, ошибаюсь, но здесь есть очень простая эвристика, поскольку она не включает много чисел, таких как 2,3,5. Мы знаем, что для любого i, j 2 ^ i * 5 ^ j следующая последовательность будет 2 ^ (i-2) * 5 ^ (j + 1). Будучи Google q, у него должно быть простое решение.

def func(i, j):
 print i, j, (2**i)*(5**j)

imax=i=2
j=0
print "i", "j", "(2**i)*(5**j)"

for k in range(20):
    func(i,j)
    j=j+1; i=i-2
    if(i<0):
        i = imax = imax+1
        j=0

Это производит вывод как:

i j (2**i)*(5**j)
2 0 4
0 1 5
3 0 8
1 1 10
4 0 16
2 1 20
0 2 25
5 0 32
3 1 40
1 2 50
6 0 64
4 1 80
2 2 100
0 3 125
7 0 128
5 1 160
3 2 200
1 3 250
8 0 256
6 1 320
d1val
источник
он может работать до 20 или 200, но в какой-то момент он начнет пропускать некоторые числа и / или выводить их в неправильном порядке.
Уилл Несс
0

Если вы идете по тому, что действительно происходит, когда мы увеличиваем I или J в выражении 2^i * 5^j , вы либо умножаете на еще 2 или еще 5. Если мы переформулируем задачу как - учитывая конкретное значение i и j, как вы найдете следующее Чем больше значение, тем становится очевидным решение.

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

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

Вот программа на Ruby:

i = j = 0                                                                       
20.times do                                                                     
  puts 2**i * 5**j

  if i > 1                                                                      
    j += 1                                                                      
    i -= 2                                                                      
  elsif j > 0                                                                   
    j -= 1                                                                      
    i += 3                                                                      
  else                                                                          
    i += 1                                                                      
  end                                                                                                                                                               
end
slowpoison
источник
Это не работает, так как 'i' никогда не становится больше 4, поэтому кратные 32 (2 ^ 5) никогда не появятся.
threenplusone
0

Если нам разрешено использовать java Collection, мы можем получить эти числа в O (n ^ 2)

public static void main(String[] args) throws Exception {
    int powerLimit = 7;  
     int first = 2;
     int second = 5;
    SortedSet<Integer> set = new TreeSet<Integer>();

    for (int i = 0; i < powerLimit; i++) {
        for (int j = 0; j < powerLimit; j++) {
            Integer x = (int) (Math.pow(first, i) * Math.pow(second, j));
            set.add(x);
        }
    }

    set=set.headSet((int)Math.pow(first, powerLimit));

    for (int p : set)
        System.out.println(p);
}

Здесь powerLimit должен быть инициализирован очень осторожно! В зависимости от того, сколько номеров вы хотите.

Кави Темре
источник
это приводит к неправильным результатам: 2 ^ 8 = 256 отсутствует до 2 ^ 6 * 5 = 320. Счетная зона треугольная, а не прямоугольная.
Уилл Несс
@WillNess How ?? Когда я устанавливаю powerLimit = 9, этот фрагмент возвращает следующие числа 1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500
кави темре
нет, он производит 100 номеров. откуда ты знаешь где остановиться? Вы должны объяснить это. --- Я упоминал 7 как присутствующий в вашем фрагменте кода. для того, чтобы это был правильный ответ, вы должны точно объяснить, как установить предел для заданного количества чисел и сколько чисел оно будет перепроизводить .
Уилл Несс
0

Вот моя попытка со Scala:

case class IndexValue(twosIndex: Int, fivesIndex: Int)
case class OutputValues(twos: Int, fives: Int, value: Int) {
  def test(): Boolean = {
    Math.pow(2,  twos) * Math.pow(5, fives) == value
  }
}

def run(last: IndexValue = IndexValue(0, 0), list: List[OutputValues] = List(OutputValues(0, 0, 1))): List[OutputValues] = {
  if (list.size > 20) {
    return list
  }

  val twosValue = list(last.twosIndex).value * 2
  val fivesValue = list(last.fivesIndex).value * 5

  if (twosValue == fivesValue) {
    val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex + 1)
    val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.fivesIndex).fives + 1)
    run(lastIndex, list :+ outputValues)
  } else if (twosValue < fivesValue) {
    val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex)
    val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.twosIndex).fives)
    run(lastIndex, list :+ outputValues)
  } else {
    val lastIndex = IndexValue(last.twosIndex, last.fivesIndex + 1)
    val outputValues = OutputValues(value = fivesValue, twos = list(last.fivesIndex).twos, fives = list(last.fivesIndex).fives + 1)
    run(lastIndex, list :+ outputValues)
  }
}

val initialIndex = IndexValue(0, 0)
run(initialIndex, List(OutputValues(0, 0, 1))) foreach println

Вывод:

OutputValues(0,0,1)
OutputValues(1,0,2)
OutputValues(2,0,4)
OutputValues(0,1,5)
OutputValues(3,0,8)
OutputValues(1,1,10)
OutputValues(4,0,16)
OutputValues(2,1,20)
OutputValues(0,2,25)
OutputValues(5,0,32)
OutputValues(3,1,40)
OutputValues(1,2,50)
OutputValues(6,0,64)
OutputValues(4,1,80)
OutputValues(2,2,100)
OutputValues(0,3,125)
OutputValues(7,0,128)
OutputValues(5,1,160)
OutputValues(3,2,200)
OutputValues(1,3,250)
OutputValues(8,0,256)
nishnet2002
источник