Question difficile pour l'entretien avec Google

Question

Un de mes amis passe un entretien pour un emploi. Une des questions de l'entretien m'a fait réfléchir, je voulais juste avoir un retour.

Il y a 2 entiers non négatifs : i et j. Étant donné l'équation suivante, trouvez une solution (optimale) pour itérer sur i et j de manière à ce que la sortie soit triée.

2^i * 5^j

Donc les premiers tours ressembleraient à ça :

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

J'ai beau essayer, je ne vois pas de modèle. Vous en pensez quoi ?

Answer 1

Vous devez garder la trace de leurs exposants individuels et de leurs sommes.

donc vous commencez par f(0,0) --> 1 maintenant tu dois incrémenter l'un d'entre eux :

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

nous savons donc que 2 est le prochain - nous savons aussi que nous pouvons incrémenter l'exposant de i jusqu'à ce que la somme dépasse 5.

Vous continuez à faire des allers-retours comme ça jusqu'à ce que vous ayez atteint le nombre de tours prévu.

Answer 2

En utilisant la programmation dynamique, vous pouvez le faire en O(n). La vérité de base est qu'aucune valeur de i et j ne peut nous donner 0, et pour obtenir 1, les deux valeurs doivent être 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
    }
}

Chaque fois que vous appelez cette fonction, vérifiez si i et j sont définis, s'ils ne sont pas nuls, remplissez alors TwoCount y FiveCount

---

Réponse C++. Désolé pour le mauvais style de codage, mais je suis pressé :(

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

Bien entendu, vous pouvez utiliser des structures de données autres que les tableaux pour augmenter dynamiquement votre espace de stockage, etc. Il s'agit juste d'une esquisse pour prouver que cela fonctionne.

Answer 3

Pourquoi ne pas essayer de regarder ça dans l'autre sens. Utilisez un compteur pour tester les réponses possibles par rapport à la formule originale. Désolé pour le pseudo-code.

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

Answer 4

Ce site est l'entrée correspondante dans l'OEIS.

Il semble possible d'obtenir la séquence ordonnée en générant les premiers termes, par exemple

1 2 4 5

puis, en partant du deuxième terme, en multipliant par 4 et 5 pour obtenir les deux termes suivants

1 2 4 5 8 10

1 2 4 5 8 10 16 20

1 2 4 5 8 10 16 20 25

et ainsi de suite...

Intuitivement, cela semble correct, mais il manque bien sûr une preuve.

Answer 5

Vous savez que log_2(5)=2.32. De là, on constate que 2^2 < 5 et 2^3 > 5.

Regardez maintenant une matrice des réponses possibles :

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

Maintenant, pour cet exemple, choisissez les numéros dans l'ordre. L'ordre serait le suivant :

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

Notez que chaque ligne commence 2 colonnes après la ligne qui la commence. Par exemple, i=0 j=1 vient directement après i=2 j=0.

Un algorithme que nous pouvons dériver de ce modèle est donc (en supposant 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);
    }
}   

NOTE : Le code ici plafonne les valeurs des exposants de i et j pour qu'ils soient inférieurs à 10. Vous pourriez facilement étendre cet algorithme pour qu'il s'adapte à toute autre limite arbitraire.

NOTE : Le temps d'exécution de cet algorithme est O(n) pour les n premières réponses.

NOTE : La complexité spatiale de cet algorithme est O(1)