Pregunta difícil de la entrevista de Google

169

Un amigo mío está entrevistando para un trabajo. Una de las preguntas de la entrevista me hizo pensar, solo quería algunos comentarios.

Hay 2 enteros no negativos: i y j. Dada la siguiente ecuación, encuentre una solución (óptima) para iterar sobre iyj de tal manera que se ordene la salida.

2^i * 5^j

Entonces las primeras rondas se verían así:

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

Por más que lo intente, no puedo ver un patrón. ¿Tus pensamientos?

Chris Eberle
fuente
63
El algoritmo óptimo en términos de tiempo del programador es generar con dos bucles anidados, luego ordenar. ¿Por qué hacen preguntas como esta?
Tom Zych
21
Es posible que pueda determinar los puntos de transición al observar qué número es mayor. 2^2 < 5pero 2^3 > 5entonces en ese punto aumentas j. Creo que puede producir la salida en O (n) en lugar de O (nlgn). @ tom-zynch dos bucles anidados es O (n ^ 2). Esta pregunta es muy válida
Mikhail el
1
Solo hay una salida, por lo que la solución óptima es O (n). Lea mi solución a continuación
Mikhail
3
Al parecer, se ha abordado una pregunta similar antes: stackoverflow.com/questions/4600048/nth-ugly-number .
1
... y el OP probablemente ya debería elegir una respuesta. Después de todo, ya tiene muchos buenos.
abeln 01 de

Respuestas:

123

Dijkstra deriva una solución elocuente en "Una disciplina de programación". Él atribuye el problema a Hamming. Aquí está mi implementación de la solución de Dijkstra.

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;
}
usuario515430
fuente
18
Enlace relevante: en.wikipedia.org/wiki/Regular_number#Algorithms . Por cierto, no creo que esta sea una muy buena pregunta de entrevista. Aquí hay un (documento escrito a mano) por Dijkstra donde proporciona y prueba un algoritmo para este problema: cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF
Elian Ebbing
Cuando el objetivo es "iterar sobre i y j" necesita menos capacidad de almacenamiento, una FIFO es suficiente. Vea mi solución de Python.
GaBorgulya 01 de
77
Cuando el objetivo es "iterar sobre i y j", no es el mismo problema.
mhum 01 de
Esta es una implementación realmente agradable, usando un mínimo de memoria. Sin embargo, es una memoria lineal aunque solo desee un número.
Thomas Ahle
1
@ThomasAhle No sé si vio esto, pero tiene un código al final que es capaz de calcular el enésimo número de forma aislada. Como, por ejemplo, un número milmillonésimo .
Will Ness el
47

Aquí hay una forma más refinada de hacerlo (más refinada que mi respuesta anterior, es decir):

imagina que los números se colocan en una matriz:

     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

lo que necesita hacer es 'caminar' esta matriz, comenzando en (0,0). También necesita realizar un seguimiento de cuáles son sus próximos movimientos posibles. Cuando comienzas (0,0)solo tienes dos opciones: (0,1)o bien (1,0): como el valor de (0,1)es menor, eliges eso. luego haga lo mismo para su próxima opción (0,2)o (1,0). Hasta el momento, tiene la siguiente lista: 1, 2, 4. Su próximo movimiento es (1,0)porque el valor allí es menor que (0,3). Sin embargo, ahora tiene tres opciones para su próximo movimiento: o (0,3), o (1,1)o (2,0).

No necesita la matriz para obtener la lista, pero sí necesita hacer un seguimiento de todas sus opciones (es decir, cuando llegue a 125+, tendrá 4 opciones).

vlad
fuente
Lo voté porque estaba pensando en la misma línea, pero en el caso general, ¿no sería algo así como O (i ^ 2 * j)? Tendría que verificar varios números para cada número que emite.
Tom Zych
1
@Tom tiene que verificar más de un número, pero no está tan mal: cuando genera números entre 125 y 625, debe mirar 4 valores. entre 625 y 3025, miras 5 valores. así que realmente, se jverifica por cada 1 salida
vlad
+1: combina con esta pregunta: stackoverflow.com/questions/5000836/search-algorithm y parece que tenemos una solución O (n).
@ Moron maldita sea, no quiero pagar $ 25 por ese algoritmo, pero parece interesante.
vlad
1
en realidad, j ~ n^0.5para el enésimo valor en una secuencia, ya que los nvalores llenan un área en el i x jplano. Entonces este algo es O(n^1.5)tiempo, con O(n^0.5)espacio. Pero existe un algoritmo de tiempo lineal con la misma compatibilidad de espacio n^0.5, y el algoritmo de mini-montón de la respuesta a continuación es O(n*log(n))tiempo con el mismo n^0.5espacio.
Will Ness
25

Usa un montón mínimo.

Pon 1.

extracto-Min. Digamos que obtienes x.

Empuje 2x y 5x en el montón.

Repetir.

En lugar de almacenar x = 2 ^ i * 5 ^ j, puede almacenar (i, j) y utilizar una función de comparación personalizada.


fuente
1
Un montón le daría tiempo a lg n en sus operaciones, lo que lleva la complejidad a n lg n.
corsiKa
@glow: Sí, no veo ninguna solución O (n) publicada hasta ahora, sin embargo :-)
@abel: Ese comentario es antiguo :-) Parece que también tendrá problemas para pasar de (1,1) a (4,0). Pero verlo como una matriz joven (ver la respuesta de vlad) en realidad permite un algoritmo de tiempo O (n).
@ Moron: No creo que haya nada malo con esa solución. Ciertamente, no hay nada malo en los primeros 30 elementos, que acabo de comprobar en este momento (eso cubriría el caso (1,1) -> (4,0)).
Abeln
@abel: Sí, en realidad no intenté ejecutarlo :-) Quizás también haya una prueba fácil de su corrección. FWIW, ya tiene mi +1.
13

Una solución basada en FIFO necesita menos capacidad de almacenamiento. Código de 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))

salida:

  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
fuente
6

Esto es muy fácil de hacer O(n)en lenguajes funcionales. La lista lde 2^i*5^jnúmeros puede definirse simplemente como 1y luego 2*ly 5*lfusionarse. Así es como se ve en 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)

La mergefunción le da un nuevo valor en tiempo constante. También lo hace mapy por lo tanto también lo hace l.

Thomas Ahle
fuente
Creo que 'k' no está definido
Su
2
vamos a llamar a esta función "fusionar" union, ya que elimina los duplicados. merge, como parte de mergesort, debe conservar duplicados provenientes de sus dos secuencias de entrada. Ver Data.List.Orderedpaquete para cosas relacionadas.
Will Ness
1
+1 para Data.List.Ordered.union. Eso lo convierte en una línea:xs = 1 : union (map (2*) xs) (map (5*) xs)
Phob
@GaBorgulya Sí, incluye cinco veces la lista, [1, 2, 4, 5,...]por lo que incluye 5*4.
Thomas Ahle
1
@Phob Sí, esta es la Data.List.Ordered.unionfunción. No debe confundirse con Data.List.union.
Thomas Ahle
5

Debe realizar un seguimiento de los exponentes individuales de ellos y cuáles serían sus sumas.

entonces comienzas con f(0,0) --> 1 ahora tienes que incrementar uno de ellos:

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

entonces sabemos que 2 es el siguiente, también sabemos que podemos incrementar el exponente de i hasta que la suma supere 5.

Sigue yendo y viniendo de esta manera hasta que esté en su número de rondas.

corsiKa
fuente
Sí lo es. Hace una operación O (1) para cada ronda. A veces haces la ronda temprano, pero cuando llegas a esa ronda no tienes que hacerlo allí, así que funciona.
corsiKa
19
¿Cómo pasas de (1,1) a (4,0)? Por favor, elabore exactamente cuál es su algoritmo.
El problema es que no solo tienes dos posibilidades incrementales, por ejemplo, no has terminado f(*,2)solo porque lo encontraste f(a1,b+1)>f(a2,b). Un enfoque incremental eventualmente generará un número ilimitado de pares vecinos a la región que ya ha generado.
tormenta el
@ user515430 proporcionó una implementación que era más de lo que podía hacer en mi hora de almuerzo, pero eso era a lo que intentaba llegar.
corsiKa 01 de
4

Usando programación dinámica puedes hacer esto en O (n). La verdad fundamental es que ningún valor de i y j puede darnos 0, y para obtener 1 ambos valores deben ser 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
    }
}

Siempre que llame a esta función, compruebe si i y j están configurados, si no son nulos, luego complete TwoCountyFiveCount


C ++ respuesta. Perdón por el mal estilo de codificación, pero tengo prisa :(

#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;
                }
        }    
}

Obviamente, puede usar estructuras de datos distintas de la matriz para aumentar dinámicamente su almacenamiento, etc. Esto es solo un boceto para demostrar que funciona.

Mikhail
fuente
44
Esto parece una respuesta interesante, pero no veo cómo funciona realmente. ¿Podría agregar más detalles?
David Brunelle
Después de estudiarlo yo mismo, realmente no veo cómo funciona. Suponiendo una división de enteros, dará exactamente el mismo resultado para 3 que para 2. Además, si las condiciones if son pruebas para no cero, nunca funcionará, ya que no hay entradas que no sean cero.
David Thornley
Publicó una versión en C ++ para todos los que no dicen. @David Sus comentarios son correctos, pero mi código original era pseudocódigo y estaba pensando en términos de secuencias de comandos, por lo que no era una división entera y distinguía entre la entrada nula y la entrada de valor 0
Mikhail
este código enumera todos los números naturales, por lo que, por comentario de @ThomasAhle a la respuesta de "Perdido en Alabama" a continuación, se necesita O(exp(sqrt(n))), para producir nnúmeros de la secuencia. Existe un algoritmo lineal , por ejemplo, tal como lo proporciona ThomasAhle.
Will Ness
1
Tienes razón. En mi opinión, O(n)significaba nser el último valor, no el número de elementos impresos, lo cual no es correcto. No sé cómo funcionan los lenguajes funcionales, o cómo funciona la fusión en tiempo constante, pero su respuesta recibió mi voto positivo
Mikhail el
2

¿Por qué no intentar mirar esto desde la otra dirección? Use un contador para probar las posibles respuestas contra la fórmula original. Perdón por el pseudocódigo.

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 
  }
}
Perdido en Alabama
fuente
Esto ocurre aproximadamente O(4^sqrt(n))porque el nthnúmero de la secuencia es de aproximadamente ese tamaño.
Thomas Ahle
2

Esta es la entrada relevante en OEIS.

Parece posible obtener la secuencia ordenada generando los primeros términos, digamos

1 2 4 5

y luego, a partir del segundo término, multiplicando por 4 y 5 para obtener los siguientes dos

1 2 4 5 8 10

1 2 4 5 8 10 16 20

1 2 4 5 8 10 16 20 25

y así...

Intuitivamente, esto parece correcto, pero por supuesto falta una prueba.

abeln
fuente
2
Incorrecto :( [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 ] Sin embargo 500 <512 = 2 ^ 9 <625.
GaBorgulya
1
@NateKerkhofs, 512 se genera pero está fuera de servicio ya que 512 es menor que el 625 ya generado; el algoritmo necesitaría más lógica para ordenar la salida. Por lo tanto, el algoritmo no es tan simple como se propone y no es el mismo algoritmo.
GordonBGood
1

Sabes que log_2 (5) = 2,32. De esto observamos que 2 ^ 2 <5 y 2 ^ 3> 5.

Ahora mira una matriz de posibles respuestas:

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 ...

Ahora, para este ejemplo, elija los números en orden. Allí ordenar sería:

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...

Tenga en cuenta que cada fila comienza 2 columnas detrás de la fila que lo inicia. Por ejemplo, i = 0 j = 1 viene directamente después de i = 2 j = 0.

Por lo tanto, un algoritmo que podemos derivar de este patrón es (supongamos que 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);
    }
}   

NOTA: El código aquí limita los valores de los exponentes de i y j a menos de 10. Puede extender fácilmente este algoritmo para que se ajuste a cualquier otro límite arbitrario.

NOTA: El tiempo de ejecución de este algoritmo es O (n) para las primeras n respuestas.

NOTA: La complejidad del espacio para este algoritmo es O (1)

KLee1
fuente
Usted escribió "cada fila comienza 2 columnas detrás de la fila que lo inicia". Sin embargo, 2 ^ 9 = 512 y 5 ^ 4 = 625, por lo que esto no es cierto para la fila 4.
GaBorgulya
@ user678105 Tienes razón. Este código no funciona Lo siento todo Este código no funciona debido al redondeo del registro y a mi suposición de que no importó.
KLee1
1
Así es como arreglas esto. En el plano (x, y) lleno de puntos con coeficientes integrales, dibuje una línea desde (0,1) a (log2 (5), 0). (0,0) está en la esquina superior izquierda. El eje X va hacia la derecha, el eje Y baja. Ahora dibuje una línea desde el punto de origen (0,0) que sea perpendicular a la primera línea. Ahora deslice la primera línea a lo largo de la segunda, más y más lejos del origen, y recoja los puntos de coordenadas enteros a medida que se cruzan. Para la secuencia generada por {2,3,5}, será un plano que se mueve en el espacio (i, j, k). Si puedes traducir esta idea en código, dame un saludo. :)
Will Ness
1

Mi implementación se basa en las siguientes ideas:

  • Use dos colas Q2 y Q5, ambas inicializadas con 1. Mantendremos ambas colas ordenadas.
  • En cada paso, elimine el elemento numérico más pequeño MIN de Q2 o Q5 e imprímalo. Si Q2 y Q5 tienen el mismo elemento, elimine ambos. Imprime este número. Esto es básicamente la fusión de dos matrices ordenadas: en cada paso, elija el elemento más pequeño y avance.
  • Poner en cola MIN * 2 a Q2 y MIN * 5 a Q5. Este cambio no rompe la invariante de Q2 / Q5 que se está ordenando, porque MIN es más alto que el número MIN anterior.

Ejemplo:

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
....

Código en 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
fuente
0

calcular los resultados y ponerlos en una lista ordenada, junto con los valores para iyj

vlad
fuente
Eso probablemente te dará agujeros en el final de tu secuencia. Por ejemplo, tendrás 2^n*5^npero no 2^(n+1)*5^(n-1)cuál es más pequeño.
Thomas Ahle
@Thomas No estoy seguro de seguir tu lógica aquí. Si calcula uno, ¿por qué no calcularía también el otro?
vlad
2
@vlad Necesitas tener un límite en tus i's y j' s, ¿no? De lo contrario, nunca llegará al estado de clasificación y, por lo tanto, nunca devolverá un solo valor. Pero para cualquier límite nque elija, su lista será defectuosa.
Thomas Ahle
@Thomas tu argumento aún no tiene sentido. El OP nunca especificó el final de su lista de resultados. Si lo hace, puedes encontrar el máximo iy j.
vlad
1
@vlad Mientras leo su respuesta, primero calcula los "resultados" / los 2^i*5^jvalores, y luego los ordena. Si no tiene un número limitado de "resultados", ¿cómo va a llegar al paso de clasificación?
Thomas Ahle
0

El algoritmo implementado por user515430 por Edsger Dijkstra (http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF) es probablemente lo más rápido posible. Llamo a cada número que es una forma de 2^i * 5^j"número especial". Ahora la respuesta de vlads sería O(i*j)pero con un algoritmo doble, uno para generar los números especiales O(i*j)y otro para ordenarlos (según el artículo vinculado también O(i*j).

Pero revisemos el algoritmo de Dijkstra (ver más abajo). En este caso, nla cantidad de números especiales que estamos generando es igual a i*j. Estamos dando vueltas una vez, 1 -> ny en cada vuelta realizamos una acción constante. Entonces este algoritmo también lo es O(i*j). Y con una constante bastante rápida y ardiente también.

Mi implementación en C ++ con GMP (contenedor de C ++) y dependencia boost::lexical_cast, aunque eso se puede eliminar fácilmente (soy flojo y ¿quién no usa Boost?). Compilado con g++ -O3 test.cpp -lgmpxx -o test. En Q6600 Ubuntu 10.10 time ./test 1000000da 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
fuente
0

Si dibuja una matriz con i como fila y j como columna, puede ver el patrón. Comience con i = 0 y luego atraviese la matriz subiendo 2 filas y derecha 1 columna hasta llegar a la parte superior de la matriz (j> = 0). Luego vaya i + 1, etc.

Entonces para i = 7 viajas así:

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

Y para i = 8:

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

Aquí está en Java subiendo a i = 9. Imprime la posición de la matriz (i, j) y el valor.

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++;
    }
}
compartimento
fuente
0

Mi intuición :

Si tomo el valor inicial como 1 donde i = 0, j = 0, entonces puedo crear los siguientes números como (2 ^ 1) (5 ^ 0), (2 ^ 2) (5 ^ 0), (2 ^ 0) * (5 ^ 1), ... es decir, 2,4,5 ..

Digamos que en cualquier momento mi número es x. entonces puedo crear los siguientes números de las siguientes maneras:

  • x * 2
  • x * 4
  • x * 5

Explicacion :

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.

Prueba de funcionamiento

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]
  • Comencemos con x = 1.

    Los siguientes tres números son 1 * 2, 1 * 4, 1 * 5 [2,4,5]; Arr [1,2,4,5]

  • Ahora x = 2

    Los siguientes tres números son [4,8,10] {Dado que 4 ya ocurrieron, lo ignoraremos} [8,10]; Arr [1,2,4,5,8,10]

  • Ahora x = 4

    Siguientes tres números [8,16,20] {8 ya ocurrió ignorarlo} [16,20] Arr [1,2,4,5,8,10,16,20]

  • x = 5

    Los siguientes tres números [10,20,25] {10,20} ya están agregados [25] Arr [1,2,4,5,8,10,16,20,25]

Condición de terminación

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

Análisis

 Time Complexity : O(K) : where k is numbers possible between i,j=0 to 
 i=m1,j=m2.
 Space Complexity : O(K)
bharatj
fuente
0

Simplemente tenía curiosidad por saber qué esperar la próxima semana y he encontrado esta pregunta.

Creo que la idea es 2 ^ i no aumenta en esos grandes pasos como 5 ^ j. Por lo tanto, aumente i siempre que el próximo paso j no sea mayor

El ejemplo en C ++ (Qt es opcional):

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 );

    }
}

La salida:

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
Valentin Heinitz
fuente
Esta solución pierde algunas combinaciones. Por ejemplo, no examina el caso donde i = 1, j = 2 cualquier caso donde i = 1 y j> 1 para el caso ..
Federico
@ Federico: ¡Tienes razón! No es de extrañar por qué he fallado en las entrevistas de Google dos veces con un intervalo de 6 años, pero casi las mismas preguntas :-)
Valentin Heinitz
0

Aqui esta mi solucion

#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 */
 }

Resultado:

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
fuente
0

Sé que probablemente estoy equivocado, pero aquí hay una heurística muy simple, ya que no involucra muchos números como 2,3,5. Sabemos que para cualquier i, j 2 ^ i * 5 ^ j la siguiente secuencia sería 2 ^ (i-2) * 5 ^ (j + 1). Al ser un google q debe tener una solución simple.

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

Esto produce resultados como:

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
fuente
puede funcionar hasta 20 o 200, pero en algún momento comenzará a omitir algunos números y / o generarlos en un orden incorrecto.
Will Ness
0

Si sigue lo que realmente sucede cuando incrementamos i o j en la expresión 2^i * 5^j, está multiplicando por otros 2 u otros 5. Si reformulamos el problema como - dado un valor particular de i y j, ¿cómo encontraría el siguiente mayor valor, la solución se hace evidente.

Aquí están las reglas que podemos enumerar de manera bastante intuitiva:

  • Si hay un par de 2s ( i > 1) en la expresión, debemos reemplazarlos con un 5 para obtener el siguiente número más grande. Por lo tanto, i -= 2y j += 1.
  • De lo contrario, si hay un 5 ( j > 0), debemos reemplazarlo con tres 2s. Así j -= 1y i += 3.
  • De lo contrario, solo debemos suministrar otros 2 para aumentar el valor al mínimo. i += 1.

Aquí está el programa en 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
veneno lento
fuente
Esto no funciona ya que 'i' nunca crece más de 4, por lo que nunca aparecerán múltiplos de 32 (2 ^ 5).
threenplusone
0

Si se nos permite usar Java Collection, entonces podemos tener estos números en 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);
}

¡Aquí powerLimit debe inicializarse con mucho cuidado! Dependiendo de cuántos números quieras.

kavi temre
fuente
esto produce resultados incorrectos: falta 2 ^ 8 = 256 antes de 2 ^ 6 * 5 = 320. El área de enumeración es triangular, no rectangular.
Will Ness
@WillNess ¿Cómo? Cuando configuro powerLimit = 9, este fragmento devuelve los siguientes números 1 2 4 5 8 10 16 20 25 32 40 50 64
8010012512816020025025620400400
no, produce 100 números. ¿Cómo sabes dónde parar? debes explicar esto. --- Me referí a 7 como presente en su fragmento de código. Para que esta sea una respuesta válida, debe explicar exactamente cómo establecer el límite para una cantidad dada de números, y cuántos números producirá en exceso .
Will Ness
0

Aquí está mi intento con 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

Salida:

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
fuente