Schwierige Frage zum Google-Interview

169

Ein Freund von mir interviewt für einen Job. Eine der Interviewfragen brachte mich zum Nachdenken, ich wollte nur ein Feedback.

Es gibt 2 nicht negative ganze Zahlen: i und j. Finden Sie anhand der folgenden Gleichung eine (optimale) Lösung, um i und j so zu durchlaufen, dass die Ausgabe sortiert wird.

2^i * 5^j

Die ersten Runden würden also so aussehen:

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

Versuchen Sie, wie ich könnte, ich kann kein Muster sehen. Ihre Gedanken?

Chris Eberle
quelle
63
Der optimale Algorithmus in Bezug auf die Programmierzeit besteht darin, mit zwei verschachtelten Schleifen zu generieren und dann zu sortieren. Warum stellen sie solche Fragen?
Tom Zych
21
Möglicherweise können Sie Übergangspunkte bestimmen, indem Sie sich ansehen, welche Zahl größer ist. 2^2 < 5aber 2^3 > 5an diesem Punkt erhöhen Sie j. Ich denke, Sie können die Ausgabe in O (n) anstatt in O (nlgn) erzeugen. @ tom-zynch zwei verschachtelte Schleifen sind O (n ^ 2). Diese Frage ist sehr gültig
Mikhail
1
Es gibt nur einen Ausgang, daher ist die optimale Lösung O (n). Lesen Sie meine Lösung unten
Mikhail
3
Eine ähnliche Frage wurde anscheinend bereits zuvor beantwortet : stackoverflow.com/questions/4600048/nth-ugly-number .
1
... und das OP sollte wahrscheinlich schon eine Antwort wählen. Immerhin hat er schon viele gute.
Abeln

Antworten:

123

Dijkstra leitet eine beredte Lösung in "A Discipline of Programming" ab. Er schreibt das Problem Hamming zu. Hier ist meine Implementierung der Dijkstra-Lösung.

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
quelle
18
Relevanter Link: en.wikipedia.org/wiki/Regular_number#Algorithms . Ich denke übrigens nicht, dass dies eine sehr gute Interviewfrage ist. Hier ist eine (handschriftliche Arbeit) von Dijkstra, in der er einen Algorithmus für dieses Problem bereitstellt und beweist: cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF
Elian Ebbing
Wenn das Ziel darin besteht, "über i und j zu iterieren", benötigen Sie weniger Speicherkapazität, ein FIFO reicht aus. Siehe meine Python-Lösung.
GaBorgulya
7
Wenn das Ziel darin besteht, "über i und j zu iterieren", ist dies nicht dasselbe Problem.
mhum
Dies ist eine wirklich schöne Implementierung mit einem Minimum an Speicher. Es ist ein linearer Speicher, auch wenn Sie nur eine Zahl möchten.
Thomas Ahle
1
@ThomasAhle Ich weiß nicht, ob Sie das gesehen haben, aber am Ende befindet sich Code, mit dem die n-te Zahl isoliert berechnet werden kann. Wie zB eine milliardste Zahl .
Will Ness
47

Hier ist eine verfeinerte Methode (verfeinert als meine vorherige Antwort):

Stellen Sie sich vor, die Zahlen werden in einer Matrix platziert:

     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

Was Sie tun müssen, ist diese Matrix zu durchlaufen, beginnend mit (0,0). Sie müssen auch verfolgen, was Ihre möglichen nächsten Schritte sind. Wenn Sie bei beginnen, haben (0,0)Sie nur zwei Möglichkeiten: entweder (0,1)oder (1,0): Da der Wert von (0,1)kleiner ist, wählen Sie diese. dann machen Sie dasselbe für Ihre nächste Wahl (0,2)oder (1,0). Bisher haben Sie folgende Liste:1, 2, 4 . Ihr nächster Schritt ist, (1,0)da der Wert dort kleiner als ist (0,3). Sie haben jetzt jedoch drei Möglichkeiten für Ihren nächsten Schritt: entweder (0,3)oder (1,1)oder (2,0).

Sie benötigen die Matrix nicht, um die Liste zu erhalten, aber Sie müssen alle Ihre Auswahlmöglichkeiten im Auge behalten (dh wenn Sie 125+ erreichen, haben Sie 4 Auswahlmöglichkeiten).

vlad
quelle
Ich habe dafür gestimmt, weil ich in die gleiche Richtung dachte, aber wäre das im Allgemeinen nicht so etwas wie O (i ^ 2 * j)? Sie müssten für jede von Ihnen ausgegebene Nummer mehrere Zahlen überprüfen.
Tom Zych
1
@ Tom Sie müssen mehr als eine Zahl überprüfen, aber es ist nicht so schlimm: Wenn Sie Zahlen zwischen 125 und 625 ausgeben, müssen Sie sich 4 Werte ansehen. zwischen 625 und 3025 betrachten Sie 5 Werte. j
Also
+1: Kombiniere mit dieser Frage: stackoverflow.com/questions/5000836/search-algorithm und es sieht so aus, als hätten wir eine O (n) -Lösung.
@Moron verdammt, ich möchte nicht 25 Dollar für diesen Algorithmus bezahlen, aber er sieht interessant aus.
Vlad
1
tatsächlich j ~ n^0.5für den n-ten Wert in einer Sequenz, da nWerte einen Bereich in der i x jEbene ausfüllen . Dieses Algo ist also O(n^1.5)Zeit mit O(n^0.5)Raum. Es gibt jedoch ein lineares Zeitalgo mit derselben Raumkomplikation n^0.5, und das Mini-Heap-Algo aus der folgenden Antwort ist O(n*log(n))Zeit mit demselben n^0.5Raum.
Will Ness
25

Verwenden Sie einen Min-Haufen.

Setzen Sie 1.

Extrakt-min. Angenommen, Sie erhalten x.

Schieben Sie 2x und 5x in den Haufen.

Wiederholen.

Anstatt x = 2 ^ i * 5 ^ j zu speichern, können Sie (i, j) speichern und eine benutzerdefinierte Vergleichsfunktion verwenden.


quelle
1
Ein Haufen würde lg n Zeit für seine Operationen geben, was die Komplexität auf n lg n erhöht.
CorsiKa
@glow: Ja, ich sehe bisher keine O (n) -Lösungen :-)
@abel: Dieser Kommentar ist alt :-) Scheint, als würde er auch Probleme haben, von (1,1) nach (4,0) zu wechseln. Das Betrachten als Matrix eines Jungen (siehe die Antwort von vlad) erlaubt jedoch tatsächlich einen O (n) -Zeitalgorithmus.
@Moron: Ich glaube nicht, dass an dieser Lösung etwas falsch ist. Sicherlich nichts Falsches an den ersten 30 Elementen, die ich gerade überprüft habe (das würde den Fall (1,1) -> (4,0) abdecken).
Abeln
@abel: Ja, ich habe nicht wirklich versucht, es auszuführen :-) Vielleicht gibt es auch einen einfachen Beweis für seine Richtigkeit. FWIW, es hat bereits meine +1.
13

Eine FIFO-basierte Lösung benötigt weniger Speicherkapazität. Python-Code.

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

Ausgabe:

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

Dies ist O(n)in funktionalen Sprachen sehr einfach . Die Liste lder 2^i*5^jNummern kann einfach als 1und dann definiert 2*lund 5*lzusammengeführt werden. So sieht es in Haskell aus:

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)

Die mergeFunktion gibt Ihnen in konstanter Zeit einen neuen Wert. So mapund so auch l.

Thomas Ahle
quelle
Ich denke, dass 'k' nicht definiert ist
Ither
2
Nennen wir unionstattdessen einfach diese "Zusammenführungs" -Funktion , da sie die Duplikate entfernt. mergeAls Teil von mergesortmüssen Duplikate aus beiden Eingabesequenzen beibehalten werden. Siehe Data.List.OrderedPaket für verwandte Sachen.
Will Ness
1
+1 für Data.List.Ordered.union. Das macht es eine Zeile:xs = 1 : union (map (2*) xs) (map (5*) xs)
Phob
@GaBorgulya Ja, es enthält das Fünffache der Liste, [1, 2, 4, 5,...]also enthält es 5*4.
Thomas Ahle
1
@Phob Ja, das ist die Data.List.Ordered.unionFunktion. Nicht zu verwechseln Data.List.union.
Thomas Ahle
5

Sie müssen die einzelnen Exponenten von ihnen und ihre Summen im Auge behalten

Sie beginnen also mit f(0,0) --> 1 einem von ihnen:

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

Wir wissen also, dass 2 der nächste ist - wir wissen auch, dass wir den Exponenten von i erhöhen können, bis die Summe 5 überschreitet.

Sie gehen so hin und her, bis Sie die gewünschte Anzahl von Runden erreicht haben.

corsiKa
quelle
Ja, so ist es. Sie führen für jede Runde eine O (1) -Operation aus. Manchmal machst du die Runde früh, aber wenn du zu dieser Runde kommst, musst du es dort nicht machen, also klappt es von selbst.
CorsiKa
19
Wie geht es von (1,1) nach (4,0)? Bitte erläutern Sie genau, was Ihr Algorithmus ist.
Das Problem ist, dass Sie nicht nur zwei inkrementelle Möglichkeiten haben - z. B. sind Sie damit nicht fertig, f(*,2)nur weil Sie das gefunden haben f(a1,b+1)>f(a2,b). Ein inkrementeller Ansatz generiert schließlich eine unbegrenzte Anzahl von Paaren neben der Region, die Sie bereits ausgegeben haben.
Comingstorm
@ user515430 lieferte eine Implementierung, die mehr war, als ich in meiner Mittagspause tun konnte, aber genau das wollte ich erreichen.
CorsiKa
4

Mit dynamischer Programmierung können Sie dies in O (n) tun. Grundwahrheit ist, dass keine Werte von i und j uns 0 geben können, und um 1 zu erhalten, müssen beide Werte 0 sein;

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

Wenn Sie diese Funktion aufrufen, überprüfen Sie, ob i und j gesetzt sind. Wenn sie nicht null sind, füllen Sie TwoCountund ausFiveCount


C ++ Antwort. Entschuldigung für den schlechten Codierungsstil, aber ich habe es eilig :(

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

Natürlich können Sie andere Datenstrukturen als das Array verwenden, um Ihren Speicher usw. dynamisch zu vergrößern. Dies ist nur eine Skizze, um zu beweisen, dass es funktioniert.

Mikhail
quelle
4
Das sieht nach einer interessanten Antwort aus, aber ich sehe nicht, wie es wirklich funktioniert. Könnten Sie weitere Details hinzufügen?
David Brunelle
Nachdem ich es selbst studiert habe, sehe ich wirklich nicht, wie es funktioniert. Unter der Annahme einer ganzzahligen Division ergibt sich für 3 genau das gleiche Ergebnis wie für 2. Wenn die if-Bedingungen Tests für Nicht-Null sind, funktioniert dies außerdem nie, da keine Einträge ungleich Null vorhanden sind.
David Thornley
Hat eine C ++ - Version für alle Neinsager veröffentlicht. @ David Ihre Kommentare sind korrekt, aber mein ursprünglicher Code war Pseudocode und ich dachte in Skripten, also nicht ganzzahlige Unterteilung und Unterscheidung zwischen Null-Eingabe und Eingabe von Wert 0
Mikhail
Dieser Code listet alle natürlichen Zahlen auf. Gemäß dem Kommentar von @ThomasAhle auf die Antwort von "Lost in Alabama" unten ist es also erforderlich O(exp(sqrt(n))), nZahlen der Sequenz zu erzeugen . Es gibt einen linearen Algorithmus, z. B. wie von ThomasAhle angegeben.
Will Ness
1
Du hast recht. Nach meinem Verständnis O(n)bedeutete dies n, der letzte Wert zu sein, nicht die Anzahl der gedruckten Elemente, was nicht korrekt ist. Ich weiß nicht, wie funktionale Sprachen funktionieren oder wie das Zusammenführen in konstanter Zeit funktioniert, aber seine Antwort erhielt meine positive Bewertung
Mikhail
2

Warum nicht versuchen, dies aus der anderen Richtung zu betrachten? Verwenden Sie einen Zähler, um die möglichen Antworten anhand der Originalformel zu testen. Entschuldigung für den Pseudocode.

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 
  }
}
In Alabama verloren
quelle
Dies läuft ungefähr, O(4^sqrt(n))weil die nthNummer der Sequenz ungefähr so ​​groß ist.
Thomas Ahle
2

Dies ist der relevante Eintrag bei OEIS.

Es scheint möglich zu sein, die geordnete Sequenz zu erhalten, indem beispielsweise die ersten Terme erzeugt werden

1 2 4 5

und dann ab dem zweiten Term mit 4 und 5 multiplizieren, um die nächsten beiden zu erhalten

1 2 4 5 8 10

1 2 4 5 8 10 16 20

1 2 4 5 8 10 16 20 25

und so weiter...

Intuitiv scheint dies richtig zu sein, aber natürlich fehlt ein Beweis.

abeln
quelle
2
Falsch :( [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 ] Jedoch 500 <512 = 2 ^ 9 <625.
GaBorgulya
1
@NateKerkhofs, 512 wird generiert, ist jedoch nicht in Ordnung, da 512 kleiner ist als der bereits generierte 625; Der Algorithmus würde weitere Logik benötigen, um die Ausgabe in Ordnung zu bringen. Daher ist der Algorithmus nicht so einfach wie vorgeschlagen und überhaupt nicht derselbe Algorithmus.
GordonBGood
1

Sie wissen, dass log_2 (5) = 2.32. Daraus ergibt sich, dass 2 ^ 2 <5 und 2 ^ 3> 5.

Schauen Sie sich nun eine Matrix möglicher Antworten an:

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

Wählen Sie nun für dieses Beispiel die Zahlen der Reihe nach aus. Dort wäre die Bestellung:

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

Beachten Sie, dass jede Zeile 2 Spalten hinter der Zeile beginnt, in der sie beginnt. Zum Beispiel kommt i = 0 j = 1 direkt nach i = 2 j = 0.

Ein Algorithmus, den wir aus diesem Muster ableiten können, ist daher (angenommen 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);
    }
}   

HINWEIS: Der Code hier begrenzt die Werte der Exponenten von i und j auf weniger als 10. Sie können diesen Algorithmus leicht erweitern, um ihn in andere beliebige Grenzen einzufügen.

HINWEIS: Die Laufzeit für diesen Algorithmus beträgt O (n) für die ersten n Antworten.

HINWEIS: Die Raumkomplexität für diesen Algorithmus beträgt O (1).

KLee1
quelle
Sie haben geschrieben "Jede Zeile beginnt 2 Spalten hinter der Zeile, die sie startet". Allerdings 2 ^ 9 = 512 und 5 ^ 4 = 625, so gilt dies nicht für Zeile 4.
GaBorgulya
@ user678105 Du hast recht. Dieser Code funktioniert nicht. Entschuldigung alle. Dieser Code funktioniert nicht, da das Protokoll abgerundet ist und ich davon ausgehe, dass es keine Rolle spielt.
KLee1
1
So beheben Sie das Problem. Zeichnen Sie auf der (x, y) -Ebene voller Punkte mit Integralkoeffizienten eine Linie von (0,1) nach (log2 (5), 0). (0,0) befindet sich in der oberen linken Ecke. Die X-Achse geht nach rechts, die Y-Achse geht nach unten. Zeichnen Sie nun eine Linie vom (0,0) Ursprungspunkt, die senkrecht zur 1. Linie verläuft. Schieben Sie nun die erste Linie entlang der zweiten, immer weiter vom Ursprung entfernt, und sammeln Sie die Punkte mit ganzzahligen Koordinaten, wenn sie überquert werden. Für eine {2,3,5} -generierte Sequenz ist es eine Ebene, die sich im (i, j, k) Raum bewegt. Wenn Sie diese Idee in Code übersetzen können, rufen Sie mich an. :)
Will Ness
1

Meine Implementierung basiert auf folgenden Ideen:

  • Verwenden Sie zwei Warteschlangen Q2 und Q5, die beide mit 1 initialisiert sind. Wir halten beide Warteschlangen in sortierter Reihenfolge.
  • Entfernen Sie bei jedem Schritt das kleinste Zahlenelement MIN aus Q2 oder Q5 und drucken Sie es aus. Wenn sowohl Q2 als auch Q5 dasselbe Element haben, entfernen Sie beide. Drucken Sie diese Nummer. Dies ist im Grunde das Zusammenführen von zwei sortierten Arrays - wählen Sie bei jedem Schritt das kleinste Element und fahren Sie fort.
  • Stellen Sie MIN * 2 in Q2 und MIN * 5 in Q5 ein. Diese Änderung unterbricht nicht die Invariante von Q2 / Q5, die sortiert wird, da MIN höher als die vorherige MIN-Nummer ist.

Beispiel:

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

Code in 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
quelle
0

Berechnen Sie die Ergebnisse und fügen Sie sie zusammen mit den Werten für iund in eine sortierte Liste einj

vlad
quelle
Das wird Ihnen wahrscheinlich Löcher am späteren Ende Ihrer Sequenz geben. ZB hast du 2^n*5^naber nicht 2^(n+1)*5^(n-1)was kleiner ist.
Thomas Ahle
@ Thomas Ich bin nicht sicher, ob ich hier deiner Logik folge. Wenn Sie einen berechnen, warum würden Sie dann nicht auch den anderen berechnen?
Vlad
2
@vlad Du musst ein Limit für deine iund deine jhaben, nicht wahr ? Andernfalls gelangen Sie nie in den Sortierstatus und geben daher niemals einen einzelnen Wert zurück. Aber für jedes Limit, das nSie wählen, wird Ihre Liste fehlerhaft sein.
Thomas Ahle
@Thomas dein Argument macht immer noch keinen Sinn. Das OP hat nie ein Ende seiner Ergebnisliste angegeben. Wenn er es tut, können Sie die max iund findenj .
Vlad
1
@vlad Während ich Ihre Antwort lese, berechnen Sie zuerst die "Ergebnisse" / die 2^i*5^jWerte und sortieren sie dann. Wenn Sie keine begrenzte Anzahl von "Ergebnissen" haben, wie kommen Sie jemals zum Sortierschritt?
Thomas Ahle
0

Der von user515430 von Edsger Dijkstra (http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF) implementierte Algorithmus ist wahrscheinlich so schnell wie möglich. Ich rufe jede Nummer an, die eine Form 2^i * 5^jeiner "speziellen Nummer" ist. Jetzt würde vlads Antwort sein, O(i*j)aber mit einem doppelten Algorithmus, einer, um die speziellen Zahlen zu generieren O(i*j)und einer, um sie zu sortieren (gemäß dem verlinkten Artikel auchO(i*j) .

Aber lassen Sie uns den Dijkstra-Algorithmus überprüfen (siehe unten). In diesem Fall nist die Anzahl der von uns generierten Sonderzahlen gleich i*j. Wir schleifen einmal 1 -> nund führen in jeder Schleife eine konstante Aktion aus. So ist dieser Algorithmus auch O(i*j). Und mit einer ziemlich blitzschnellen Konstante auch.

Meine Implementierung in C ++ mit GMP (C ++ - Wrapper) und Abhängigkeit davon boost::lexical_cast, obwohl das leicht entfernt werden kann (ich bin faul und wer verwendet Boost nicht?). Zusammengestellt mit g++ -O3 test.cpp -lgmpxx -o test. Auf Q6600 time ./test 1000000gibt Ubuntu 10.10 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
quelle
0

Wenn Sie eine Matrix mit i als Zeile und j als Spalte zeichnen, können Sie das Muster sehen. Beginnen Sie mit i = 0 und durchlaufen Sie dann einfach die Matrix, indem Sie 2 Zeilen und 1 Spalte nach rechts gehen, bis Sie den oberen Rand der Matrix erreichen (j> = 0). Dann gehe ich + 1, etc ...

Für i = 7 reisen Sie also wie folgt:

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

Und für i = 8:

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

Hier ist es in Java bis zu i = 9. Es gibt die Matrixposition (i, j) und den Wert aus.

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++;
    }
}
Cubby
quelle
0

Meine Intuition :

Wenn ich den Anfangswert als 1 nehme, wobei i = 0, j = 0 ist, kann ich die nächsten Zahlen als (2 ^ 1) (5 ^ 0), (2 ^ 2) (5 ^ 0), (2 ^ 0) erstellen. * (5 ^ 1), ... dh 2,4,5 ..

Nehmen wir an, meine Nummer ist zu jedem Zeitpunkt x. dann kann ich die nächsten Zahlen auf folgende Weise erstellen:

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

Erklärung :

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.

Testlauf

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]
  • Beginnen wir mit x = 1.

    Die nächsten drei Zahlen sind 1 * 2, 1 * 4, 1 * 5 [2,4,5]; Arr [1,2,4,5]

  • Jetzt ist x = 2

    Die nächsten drei Zahlen sind [4,8,10] {Da 4 bereits aufgetreten sind, werden wir sie ignorieren} [8,10]; Arr [1,2,4,5,8,10]

  • Jetzt ist x = 4

    Die nächsten drei Zahlen [8,16,20] {8 sind bereits aufgetreten, ignorieren Sie es} [16,20] Arr [1,2,4,5,8,10,16,20]

  • x = 5

    Die nächsten drei Zahlen [10,20,25] {10,20} bereits [25] werden hinzugefügt Arr [1,2,4,5,8,10,16,20,25]

Kündigungsbedingung

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

Analyse

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

War nur neugierig was mich nächste Woche erwartet und habe diese Frage gefunden.

Ich denke, die Idee ist 2 ^ i steigt nicht in diesen großen Schritten als 5 ^ j. Erhöhen Sie also i, solange der nächste J-Schritt nicht größer ist.

Das Beispiel in C ++ (Qt ist optional):

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

    }
}

Die Ausgabe:

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
quelle
Bei dieser Lösung fehlen einige Kombinationen. Zum Beispiel wird der Fall, in dem i = 1, j = 2 ist, nicht untersucht, in jedem Fall, in dem i = 1 und j> 1 sind.
Federico
@ Federico: Du hast recht! Kein Wunder, warum ich Google-Interviews zweimal im Abstand von 6 Jahren nicht bestanden habe, aber fast die gleichen Fragen :-)
Valentin Heinitz
0

Hier ist meine Lösung

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

Ergebnis:

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

Ich weiß, dass ich wahrscheinlich falsch liege, aber hier gibt es eine sehr einfache Heuristik, da sie nicht viele Zahlen wie 2,3,5 enthält. Wir wissen, dass für jedes i, j 2 ^ i * 5 ^ j die nächste Sequenz 2 ^ (i-2) * 5 ^ (j + 1) wäre. Als Google Q muss es eine einfache Lösung geben.

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

Dies erzeugt eine Ausgabe als:

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
quelle
Es kann bis zu 20 oder 200 funktionieren, aber irgendwann werden einige Zahlen übersprungen und / oder in falscher Reihenfolge ausgegeben.
Will Ness
0

Wenn Sie sich an das halten, was wirklich passiert, wenn wir i oder j im Ausdruck erhöhen 2^i * 5^j erhöhen, multiplizieren Sie entweder mit einer anderen 2 oder einer anderen 5. Wenn wir das Problem als - bei einem bestimmten Wert von i und j wiederholen, wie würden Sie den nächsten finden? Bei größerem Wert wird die Lösung offensichtlich.

Hier sind die Regeln, die wir intuitiv aufzählen können:

  • Wenn i > 1der Ausdruck ein Paar von 2s ( ) enthält, sollten wir sie durch eine 5 ersetzen, um die nächstgrößere Zahl zu erhalten. Also i -= 2und j += 1.
  • Andernfalls j > 0müssen wir eine 5 ( ) durch drei 2s ersetzen. Also j -= 1und i += 3.
  • Andernfalls müssen wir nur weitere 2 angeben, um den Wert um ein Minimum zu erhöhen. i += 1.

Hier ist das Programm in 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
schleichendes Gift
quelle
Dies funktioniert nicht, da 'i' niemals größer als 4 wird, sodass niemals ein Vielfaches von 32 (2 ^ 5) erscheint.
Threenplusone
0

Wenn wir Java Collection verwenden dürfen, können wir diese Nummer in O (n ^ 2) haben.

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

Hier muss powerLimit sehr sorgfältig initialisiert werden !! Abhängig davon, wie viele Nummern Sie möchten.

kavi temre
quelle
Dies führt zu falschen Ergebnissen: 2 ^ 8 = 256 fehlt vor 2 ^ 6 * 5 = 320. Der Aufzählungsbereich ist dreieckig und nicht rechteckig.
Will Ness
@ WillNess Wie? Wenn ich powerLimit = 9 setze, gibt dieses Snippet die folgenden Zahlen zurück: 1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500
kavi temre
Nein, es werden 100 Zahlen erzeugt. Woher weißt du, wo du aufhören sollst? du musst das erklären. --- Ich habe 7 als in Ihrem Code-Snippet vorhanden bezeichnet. Damit dies eine gültige Antwort ist, müssen Sie genau erklären, wie Sie das Limit für eine bestimmte Anzahl von Zahlen festlegen und wie viele Zahlen es überproduzieren wird .
Will Ness
0

Hier ist mein Versuch mit 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

Ausgabe:

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
quelle