Größte GCD zwischen einigen Zahlen

StackOverflow https://stackoverflow.com/questions/3668126

Frage

Wir haben einige nicht-negative Zahlen bekommen. Wir wollen das Paar mit maximalen gcd finden. eigentlich dieses Maximum ist wichtiger als das Paar! Zum Beispiel, wenn wir haben:

2 4 5 15

gcd (2,4) = 2

gcd (2,5) = 1

gcd (2,15) = 1

gcd (4,5) = 1

gcd (4,15) = 1

gcd (5,15) = 5

Die Antwort ist 5.

War es hilfreich?

Lösung

Es gibt eine Lösung, die O (n) nehmen würde:

Lassen Sie unsere Zahlen a_i sein. Zuerst berechnen m=a_0*a_1*a_2*.... Für jede Zahl a_i, berechnen gcd(m/a_i, a_i). Die Zahl, die Sie suchen, ist das Maximum dieser Werte.

Ich habe nicht bewiesen, dass dies immer der Fall ist, aber in Ihrem Beispiel, funktioniert es:

m=2*4*5*15=600,

max(gcd(m/2,2), gcd(m/4,4), gcd(m/5,5), gcd(m/15,15))=max(2, 2, 5, 5)=5

Hinweis: Dies ist nicht korrekt. Wenn die Zahl a_i hat einen Faktor p_j zweimal wiederholt, und wenn zwei andere Zahlen auch diesen Faktor, p_j enthalten, erhalten Sie das falsche Ergebnis p_j^2 von p_j insted. Zum Beispiel für den Satz 3, 5, 15, 25, erhalten Sie 25 als Antwort statt 5.

Sie können jedoch diese Funktion dazu nutzen, um schnell Zahlen herauszufiltern. Zum Beispiel in dem oben genannten Fall, wenn Sie die 25 bestimmen, können Sie zunächst die erschöpfende Suche tun für a_3=25 mit gcd(a_3, a_i) das realen Maximum, 5 zu finden, dann herauszufiltern gcd(m/a_i, a_i), i!=3, die weniger als oder gleich 5 (im Beispiel oben , diese filtert alle anderen).

hinzugefügt zur Klärung und Begründung :

Um zu sehen, warum das funktionieren sollte, beachten Sie, dass gcd(a_i, a_j) dividieren für alle gcd(m/a_i, a_i) j!=i.

Lassen Sie uns Anruf gcd(m/a_i, a_i) als g_i und max(gcd(a_i, a_j),j=1..n, j!=i) als r_i. Was ich oben gesagt ist g_i=x_i*r_i und x_i eine ganze Zahl. Es ist offensichtlich, dass r_i <= g_i, so in n gcd Operationen, wir eine obere Schranke für r_i für alle i erhalten.

Die obige Behauptung ist nicht sehr offensichtlich. Betrachten wir es tiefer ein bisschen zu sehen, warum es wahr ist: die gcd von a_i und a_j das Produkt aller Primfaktoren ist, die sowohl in a_i und a_j erscheinen (per Definition). Nun multiplizieren mit einer anderen Nummer, a_j b. Die GCD von a_i und b*a_j entweder gleich gcd(a_i, a_j) oder ein Vielfaches davon, weil b*a_j alle Primfaktoren von a_j enthält, und einige mehr Primfaktoren trugen durch b, die auch in der Faktorisierung von a_i enthalten sein können. In der Tat, gcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j), glaube ich. Aber ich kann nicht einen Weg finden, um davon Gebrauch zu machen. :)

Wie auch immer, in unserer Konstruktion ist m/a_i einfach eine Verknüpfung, um das Produkt aller a_j zu berechnen, wo j=1..1, j!=i. Als Ergebnis enthält gcd(m/a_i, a_i) alle gcd(a_i, a_j) als Faktor. Also, natürlich, wird das Maximum dieser einzelnen gcd Ergebnisse teilen g_i.

Nun ist der größte g_i ist von besonderem Interesse für uns: es ist entweder die maximale gcd selbst (wenn x_i 1), oder ein guter Kandidat für eine zu sein. Um das zu tun, tun wir noch n-1 gcd Operationen und berechnen r_i explizit. Dann ziehen wir alle g_j weniger als oder gleich r_i als Kandidaten. Wenn wir keine andere Kandidaten übrig haben, sind wir fertig. Wenn nicht, holen wir die nächste größte g_k und berechnen r_k auf. Wenn r_k <= r_i ziehen wir g_k, und wiederholen Sie mit anderen g_k'. Wenn r_k > r_i, wir verbleibenden g_j <= r_k herauszufiltern, und wiederholen.

Ich denke, es ist möglich, eine Reihe Satz zu konstruieren, die diesen Algorithmus laufen in O machen (n ^ 2) (wenn wir nicht alles, um herauszufiltern), aber auf Zufallszahl-Sets, ich denke, es wird schnell loswerden große Teile der Kandidaten.

Andere Tipps

Sie können den euklidischen Algorithmus verwenden, um die GCD von zwei Zahlen zu finden. 

while (b != 0) 
{
    int m = a % b;
    a = b;
    b = m;
}
return a;

Wenn Sie eine Alternative zu dem offensichtlichen Algorithmus wollen, dann vorausgesetzt, Ihre Zahlen in einem begrenzten Bereich, und Sie vielen Speicher haben, können Sie O (N ^ 2) Zeit schlagen, N die Anzahl von Werten:

  • Erzeugen einer Reihe einer kleinen Integer-Typ, Indizes 1 an den Eingang max. O (1)
  • Für jeden Wert, erhöht die Anzahl der jedes Element des Index, die ein Faktor der Zahl ist (stellen Sie sicher, dass Sie nicht WrapAround tun). O (N).
  • Ab Ende des Feldes, bis Sie Scan-Rück Wert finden> = 2 O (1)

Das sagt man den Max gcd, aber nicht sagen, welches Paar es produziert. Für Ihr Beispiel Eingabe, die berechneten Array sieht wie folgt aus: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 2 1 1 2 0 0 0 0 0  0  0  0  0  1

Ich weiß nicht, ob dies für die Eingänge tatsächlich schneller ist, Sie zu behandeln haben. Die konstanten Faktoren beteiligt sind groß. Die gebundene auf Ihre Werte und die Zeit, um einen Wert innerhalb dieses gebunden Faktorisierung

Sie müssen nicht jeden Wert Faktorisierung - Sie Memoisation und / oder eine vorgenerierte Liste der Primzahlen nutzen könnten. Was die Idee gibt mir, dass, wenn Sie die Faktorisierung sind memoising, müssen Sie das Array nicht brauchen:

  • Erstellen Sie eine leere Reihe von int, und ein Best-so-far Wert 1.
  • Für jeden Eingang integer:
    • , wenn es weniger als oder gleich am besten so weit, weiter.
    • Überprüfen Sie, ob es in dem Satz ist. Wenn ja, am besten so weit = max (am besten so weit, dieser Wert), weiter. Wenn nicht:
      • fügen Sie es dem Satz
      • Wiederholung für alle seine Faktoren (größer als am besten so weit).

Hinzufügen / Nachschlagen in einem Satz könnte O (log N) sein, obwohl es, was Strukturdaten ab, die Sie verwenden. Jeder Wert hat O (f (k)) Faktoren, wobei k der Maximalwert ist, und ich kann mich nicht erinnern, was die Funktion f ...

Der Grund, dass Sie mit einem Wert so schnell fertig sind, wie Sie es in der Gruppe begegnen, ist, dass Sie eine Nummer gefunden haben, die ein gemeinsamer Faktor von zwei Eingangswerten ist. Wenn Sie es nicht Faktorisierung, werden Sie nur kleinere solche Zahlen finden, die nicht interessant sind.

Ich bin mir nicht ganz sicher, was der beste Weg für die größeren Faktoren zu wiederholen ist. Ich denke, in der Praxis Du vielleicht einen Mittelweg haben: Sie wollen sie nicht ganz in absteigender Reihenfolge zu tun, weil es schwierig ist bestellt Faktoren zu erzeugen, aber Sie wollen ja auch nicht, um tatsächlich alle Faktoren finden

.

Auch in den Bereichen O (N ^ 2), könnten Sie in der Lage sein, die Verwendung des euklidischen Algorithmus zu schlagen:

Fully jede Zahl faktorisieren, es als eine Folge von Exponenten der Primzahlen Speicher (so beispielsweise 2 {1}, 4 ist {2}, 5 ist {0, 0, 1} 15 ist {0, 1, 1}). Dann können Sie gcd (a, b), indem der Minimalwert bei jedem Index berechnen und multipliziert sie wieder aus. Keine Ahnung, ob dies ist schneller als Euclid im Durchschnitt, aber es könnte sein. Offensichtlich verwendet es eine Last mehr Speicher.

Die Optimierungen ich denken kann, ist

1) mit den beiden größten Zahlen beginnen, da sie wahrscheinlich haben die meisten Primfaktoren sind und somit wahrscheinlich die meisten gemeinsamen Primfaktoren haben (und damit die höchste GCD).

2) Wenn die GCDS von anderen Paaren Berechnung können Sie Ihre euklidische Algorithmus Schleife stoppen, wenn Sie unter Ihrem aktuellen größten GCD erhalten.

Aus der Spitze von meinem Kopf kann ich nicht so denken, dass Sie, ohne versuchen zu arbeiten, jedes Paar einzeln die größte GCD eines Paares arbeiten können (und ein bisschen wie oben optimieren).

Disclaimer: Ich habe noch nie an diesem Problem sieht vor und die oben ist aus der Spitze von meinem Kopf. Es kann eine bessere Art und Weise sein, und ich kann falsch sein. Ich bin glücklich, meine Gedanken in mehr Länge zu diskutieren, wenn jemand will. :)

Es gibt keine O(n log n) Lösung für dieses Problem im Allgemeinen. In der Tat ist der schlimmste Fall in der Anzahl der Elemente in der Liste O(n^2). Betrachten Sie die folgende Reihe von Zahlen: 

2^20 3^13 5^9 7^2*11^4 7^4*11^3

Nur der GCD der letzt beide ist größer als 1, aber der einzige Weg, zu wissen, dass bei der GCDS von der Suche ist jedes Paar und Ankündigung zu versuchen, dass einer von ihnen größer als 1 ist.

So Sie sitzen fest mit dem langweiligen Brute-Force-Try-every-pair Ansatz, vielleicht mit ein paar cleveren Optimierungen tun unnötige Arbeit zu vermeiden, wenn Sie bereits eine große GCD gefunden (gleichzeitig aber dafür sorgen, dass Sie don‘ t verpassen nichts).

Mit einigen Einschränkungen, beispielsweise die Zahlen in der Anordnung sind in einem gegebenen Bereich, sagen 1-1e7, ist es machbar, in O (NlogN) / A (MAX * LogMax), wobei max der maximal mögliche Wert in A.

Inspiriert vom Siebalgorithmus, und kam über sie in einem Hackerrank Challenge- - gibt es für zwei Arrays durchgeführt. Überprüfen Sie ihre redaktionellen.

  • finden min (A) und max (A) - O (N)
    erzeugt eine binäre Maske, um Marke, die Elemente von A im angegebenen Bereich erscheinen, für O (1) lookup; O (N) zu errichten; O (MAX_RANGE) Speicher.
  • für jede Zahl a im Bereich (min (A), max (A)):
    für AA = a; aa
  • , wenn aa in A, erhöht einen Zähler für aa, und vergleichen Sie es mit Strom max_gcd, wenn Zähler> = 2 (das heißt, Sie haben zwei Zahlen durch aa teilbar);
  • Speicher oben zwei Kandidaten für jeden GCD Kandidaten.
  • könnte auch Elemente ignorieren, die weniger als Strom max_gcd;

Zurück Antwort: Noch O (N ^ 2) - Sortierung der Array; einige der unnötigen Vergleiche beseitigen sollte; 

max_gcd = 1
# assuming you want pairs of distinct elements.
sort(a) # assume in place
for ii = n - 1: -1 : 0 do
    if a[ii] <= max_gcd
        break
    for jj = ii - 1 : -1 :0 do
        if a[jj] <= max_gcd 
            break
        current_gcd = GCD(a[ii], a[jj])
        if current_gcd > max_gcd:
            max_gcd = current_gcd

Dies sollte einige unnötige Berechnung speichern.

Pseudo-Code 

function getGcdMax(array[])

    arrayUB=upperbound(array)
    if (arrayUB<1)
        error
    pointerA=0
    pointerB=1

    gcdMax=0

    do
        gcdMax=MAX(gcdMax,gcd(array[pointera],array[pointerb]))
        pointerB++
        if (pointerB>arrayUB)
            pointerA++
            pointerB=pointerA+1
    until (pointerB>arrayUB)

    return gcdMax
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top