Imprime le plus petit suivant de 2 ^ i * 5 ^ j où i, j> = 0

On m'a posé cette question lors d'une projection téléphonique technique récemment et je n'ai pas bien fait. La question est incluse mot pour mot ci-dessous.

Générez une {2^i * 5^j | i,j >= 0}collection triée. Imprimez en continu la plus petite valeur suivante.

Exemple: { 1, 2, 4, 5, 8, 10...}

«Le plus petit suivant» me fait penser qu'il y a un tas de min, mais je ne savais pas vraiment où aller à partir de là et aucune aide n'a été fournie par l'intervieweur.

Quelqu'un a-t-il des conseils sur la façon de résoudre un tel problème?

Reformulons le problème: sortie de chaque nombre de 1 à l'infini de telle sorte que le nombre n'a aucun facteur sauf 2 et 5.

Ci-dessous, un simple extrait 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);
}

L' approche de Kilian / QuestionC est beaucoup plus performante. Extrait C # avec cette approche:

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 empêche les insertions en double.

Fondamentalement, cela fonctionne en s'assurant que le numéro suivant de la séquence est bien itms.

Preuve de la validité de cette approche:
l'algorithme décrit garantit qu'après n'importe quel nombre sorti dans le formulaire 2^i*5^j, l'ensemble contient maintenant 2^(i+1)*5^jet 2^i*5^(j+1). Supposons que le nombre suivant de la séquence soit 2^p*5^q. Il doit exister un numéro de sortie précédemment de la forme 2^(p-1)*5^(q)ou 2^p*5^(q-1)(ou les deux, si ni p ni q ne sont égaux à 0). Sinon, ce 2^p*5^qn'est pas le numéro suivant, car 2^(p-1)*5^(q)et 2^p*5^(q-1)sont tous deux plus petits.

Le deuxième extrait utilise de la O(n)mémoire (où n est le nombre de nombres qui ont été sortis), car O(i+j) = O(n)(car i et j sont tous deux inférieurs à n), et trouvera n nombres dans le O(n log n)temps. Le premier extrait trouve des nombres dans un temps exponentiel.

Il s'agit d'une question d'entrevue suffisamment courante pour qu'il soit utile de connaître la réponse. Voici l'entrée pertinente dans ma feuille de lit personnel:

• pour générer les nombres du formulaire 3 ^a 5 ^b 7 ^c dans l'ordre , commencez par 1, placez les trois successeurs possibles (3, 5, 7) dans une structure auxiliaire, puis ajoutez le plus petit nombre de celui-ci à votre liste.

En d'autres termes, vous avez besoin d'une approche en deux étapes avec un tampon trié supplémentaire pour résoudre ce problème efficacement. (Une bonne description plus longue est dans Cracking the Coding Interview de Gayle McDowell.

Voici une réponse qui s'exécute avec une mémoire constante, au détriment du CPU. Ce n'est pas une bonne réponse dans le contexte de la question d'origine (c'est-à-dire une réponse lors d'un entretien). Mais si l'interview dure 24 heures, ce n'est pas si mal. ;)

L'idée est que si j'ai n qui est une réponse valide, alors la suivante dans la séquence va être n fois une puissance de deux, divisée par une puissance de 5. Ou bien n fois une puissance de 5, divisée par un puissance de deux. Pourvu qu'il se divise également. (... ou le diviseur peut être 1;) auquel cas vous multipliez simplement par 2 ou 5)

Par exemple, pour passer de 625 à 640, multipliez par 5 ** 4/2 ** 7. Ou, plus généralement, multipliez par une valeur de 2 ** m * 5 ** npour m, n où l'on est positif et l'autre négatif ou nul, et le multiplicateur divise le nombre également.

Maintenant, la partie délicate est de trouver le multiplicateur. Mais nous savons a) le diviseur doit diviser le nombre également, b) le multiplicateur doit être supérieur à un (les nombres continuent d'augmenter), et c) si nous choisissons le plus petit multiplicateur supérieur à 1 (c'est-à-dire 1 <f <tous les autres f ), alors c'est garanti d'être notre prochaine étape. L'étape qui suivra sera son étape la plus basse.

La partie désagréable est de trouver la valeur de m, n. Il n'y a que des possibilités de log (n), car il n'y a que tant de 2 ou de 5 à abandonner, mais j'ai dû ajouter un facteur de -1 à +1 comme manière bâclée pour gérer l'arrondi. Il suffit donc d'itérer à travers O (log (n)) à chaque étape. C'est donc O (n log (n)) dans l'ensemble.

La bonne nouvelle est que, comme il prend une valeur et trouve la valeur suivante, vous pouvez commencer n'importe où dans la séquence. Donc, si vous voulez le suivant après 1 milliard, il peut simplement le trouver en itérant à travers les 2/5 ou 5/2 et en choisissant le plus petit multiplicateur supérieur à 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

J'ai validé les 10 000 premiers numéros générés par rapport aux 10 000 premiers générés par la solution de liste triée, et cela fonctionne au moins jusque-là.

BTW le suivant après un billion semble être 1 024 000 000 000.

...

Hm. Je peux obtenir des performances O (n) - O (1) par valeur (!) - et l'utilisation de la mémoire O (log n) en traitant best()comme une table de recherche que j'étends de manière incrémentielle. À l'heure actuelle, il économise de la mémoire en itérant à chaque fois, mais il fait beaucoup de calculs redondants. En maintenant ces valeurs intermédiaires - et une liste de valeurs min - je peux éviter le travail en double et l'accélérer beaucoup. Cependant, la liste des valeurs intermédiaires augmentera avec n, d'où la mémoire O (log n).

Brian avait absolument raison - mon autre réponse était bien trop compliquée. Voici un moyen plus simple et plus rapide de le faire.

Imaginez le quadrant I du plan euclidien, limité aux entiers. Appelez un axe l'axe i et l'autre axe l'axe j.

Évidemment, les points proches de l'origine seront choisis avant les points éloignés de l'origine. Notez également que la zone active s'éloignera de l'axe i avant de s'éloigner de l'axe j.

Une fois qu'un point a été utilisé, il ne sera plus jamais utilisé. Et un point ne peut être utilisé que si le point situé juste en dessous ou à gauche a déjà été utilisé.

En les assemblant, vous pouvez imaginer une "frontière" ou un "bord d'attaque" qui commence autour de l'origine et se propage vers le haut et vers la droite, s'étalant le long de l'axe i plus loin que sur l'axe j.

En fait, nous pouvons comprendre quelque chose de plus: il y aura au plus un point sur la frontière / le bord pour une valeur i donnée. (Vous devez incrémenter i plus de 2 fois pour égaler un incrément de j.) Ainsi, nous pouvons représenter la frontière comme une liste contenant un élément pour chaque coordonnée i, ne variant qu'avec la coordonnée j et la valeur de la fonction.

À chaque passage, nous sélectionnons l'élément minimum sur le bord d'attaque, puis le déplaçons une fois dans la direction j. S'il se trouve que nous élevons le dernier élément, nous ajoutons un nouveau dernier élément supplémentaire avec une valeur i incrémentée et une valeur j de 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;
            }
        }
    }
}

Espace: O (n) en nombre d'éléments imprimés jusqu'à présent.

Vitesse: O (1) inserts, mais ceux-ci ne sont pas effectués à chaque fois. (Parfois plus long quand le List<>doit croître, mais toujours O (1) amorti). Le grand puits de temps est la recherche du minimum, O (n) dans le nombre d'éléments imprimés jusqu'à présent.

La solution basée sur l'ensemble était probablement ce que votre enquêteur recherchait, mais elle a la conséquence malheureuse d'avoir de la O(n)mémoire et du O(n lg n)temps total pour les néléments de séquençage .

Un peu de mathématiques nous aide à trouver une solution d' O(1)espace et de O(n sqrt(n))temps. Remarquez cela 2^i * 5^j = 2^(i + j lg 5). Trouver les premiers néléments de {i,j > 0 | 2^(i + j lg 5)}réduit à trouver les premiers néléments de {i,j > 0 | i + j lg 5}parce que la fonction (x -> 2^x)est strictement monotone croissante, la seule façon pour certains a,bqui 2^a < 2^best si a < b.

Maintenant, nous avons juste besoin d'un algorithme pour trouver la séquence de i + j lg 5, où i,jsont les nombres naturels. En d'autres termes, étant donné notre valeur actuelle de i, j, ce qui minimise le prochain mouvement (c'est-à-dire nous donne le nombre suivant dans la séquence), c'est une augmentation de l'une des valeurs (disons j += 1) avec une diminution de l'autre ( i -= 2). La seule chose qui nous limite, c'est cela i,j > 0.

Il n'y a que deux cas à considérer - des iaugmentations ou des jaugmentations. L'un d'eux doit augmenter car notre séquence augmente, et les deux n'augmentent pas car sinon nous sautons le terme dans lequel nous n'avons qu'un seul d' i,jaugmentation. Ainsi, l'un augmente et l'autre reste le même ou diminue. Exprimé en C ++ 11, l'ensemble de l'algorithme et sa comparaison avec la solution définie sont disponibles ici .

Cela permet d'obtenir une mémoire constante car il n'y a qu'une quantité constante d'objets alloués dans la méthode, en dehors du tableau de sortie (voir lien). La méthode réalise le temps logarithmique à chaque itération car pour tout donné (i,j), elle parcourt pour la meilleure paire (a, b)telle que (i + a, j + b)la plus petite augmentation de la valeur de i + j lg 5. Cette traversée est 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)

Toutes les tentatives d'itération pour mettre à jour i, puis j, et va de pair avec la plus petite mise à jour des deux.

Depuis iet tout jau plus O(sqrt(n)), nous avons du O(n sqrt(n))temps total . iet jcroître au taux du carré de npuisque pour toutes les valeurs maximales imaxet jmaxil existe O(i j)des paires uniques à partir desquelles faire notre séquence si notre séquence est des ntermes, et iet jcroître dans un facteur constant les uns des autres (parce que l'exposant est composé d'un linéaire combinaison des deux), nous le savons iet le jsommes O(sqrt(n)).

Il n'y a pas grand-chose à craindre en ce qui concerne l'erreur en virgule flottante - puisque les termes croissent de façon exponentielle, nous aurions à faire face au débordement avant que l'erreur de flop ne nous rattrape, de plusieurs magnitudes. J'y ajouterai plus de discussion si j'ai le temps.