Gegeben ein array von ganzen zahlen, finden die GRÖßTE Zahl mit den Ziffern der Reihe, so dass es durch 3 teilbar

E. g.: Array: 4,3,0,1,5 {Anzunehmen, dass alle Ziffern sind >=0. Auch jedes element im array entspricht einer Ziffer. d.h. jedes element im array wird zwischen 0 und 9. }

In der obigen array die größte Zahl ist: 5430 {mit Ziffern 5, 4, 3 und 0 aus dem array}

Mein Ansatz:

Für die Teilbarkeit durch 3, müssen wir die Summe der Ziffern ist teilbar durch 3.
So,

  1. Schritt 1: Entfernen Sie alle Nullen aus dem array.
  2. Schritt 2: Diese Nullen kommen an das Ende. {Da Sie keinen Einfluss auf die Summe, und wir finden, die größte Zahl}
  3. Schritt 3: Finden Sie die Teilmenge der Elemente des Arrays (ohne Nullen), so dass die Anzahl der Ziffern ist MAXIMAL und auch, dass die Summe der Ziffern ist MAXIMAL und die Summe ist durch 3 teilbar.
  4. SCHRITT 4: Die erforderliche Ziffer besteht aus den Ziffern in der obigen Ergebnismenge in absteigender Reihenfolge.

So, der wichtigste Schritt ist SCHRITT 3, d.h. Wie finden Sie die Teilmenge, so dass es enthält die MAXIMAL mögliche Anzahl von Elementen, so dass Ihre Summe ist MAX und ist durch 3 teilbar .

Ich dachte, vielleicht Schritt 3 getan werden könnte, die von GIERIGEN WAHL unter all den Elementen und halten Sie zum entfernen des kleinsten Elements im set, bis die Summe ist durch 3 teilbar.

Aber ich bin nicht davon überzeugt, dass dieser GREEDY-Wahl funktioniert.

Bitte sagen, ob mein Ansatz richtig ist.
Wenn es so ist, dann bitte vorschlagen, wie zu tun, Schritt-3 ?

Bitte auch vorschlagen, andere möglich/effizienten Algorithmus.

Was ist mit brute-force zu generieren, die Möglichkeiten ? Das ist generatif alle die Kombination, die durch 3 teilbar, und nehmen Sie dann die größte ?
Schritt 3 ist ein bisschen ähnlich wie subset-sum-problem, aber es riecht auch einfacher (so könnte es sein solveable polynomially, nachdem alle). Aber ich bezweifle, gierig wird hier zu arbeiten.
Ja, Brute-Force ist immer eine option. Aber ich war hinking, wenn es getan werden könnte, in der einige effiziente Weg.
Wenn wir die Teilmenge-Summe Ansatz, dann müssen wir betrachten alle vielfachen von 3: 3, 2*3, 3*3, 4*3 .. und so weiter... Also ich denke, dass würde sich dann exponential nur.
Hier ist meine Idee : entfernen Sie die Nullen, werden Sie am Ende Hinzugefügt, wie du gesagt hast. N nicht-null-Ziffern bleiben Sie dann generieren Sie alle Möglichkeiten mit der maximalen Länge N. wenn Sie etwas finden, nehmen Sie den maximalen Wert. Vielleicht Sortieren die Ziffern in absteigender Reihenfolge schneller sein können. Wenn Sie nicht etwas finden, suchen Sie für alle Möglichkeiten, die mit der Länge N-1, und so weiter, bis Sie etwas finden.

InformationsquelleAutor user1599964 | 2012-09-19

  1. 17

    Beobachtung:, Wenn man eine Zahl ist durch 3 teilbar, Sie müssen nehmen die meisten 2 zahlen, um die optimale Lösung.

    Einem einfachen O(n^2) Lösung wird es sein, prüfen Sie alle Möglichkeiten, um entfernen 1 Anzahl, und wenn keiner gültig ist, überprüfen Sie alle Paare (Es gibt O(n^2)).

    EDIT:

    O(n) Lösung: Erstellen Sie 3 Eimer - bucket1, bucket2, bucket0. Jeder wird bezeichnen das Modul 3 mit dem Wert der zahlen. Ignorieren bucket0 in den nächsten Algorithmus.

    Lassen Sie die Summe der Reihe sein sum. 

    If sum % 3 ==0: we are done.
else if sum % 3 == 1:
  if there is a number in bucket1 - chose the minimal
  else: take 2 minimals from bucket 2
else if sum % 3 == 2
  if there is a number in bucket2 - chose the minimal
  else: take 2 minimals from bucket1

    Hinweis: Sie müssen nicht wirklich brauchen, den Eimer zu erreichen O(1) Platz - Sie müssen nur die 2 minimalen Werte von bucket1 und bucket2, denn es ist die einzige Zahl, die wir eigentlich aus dieser Eimer.

    Beispiel:

    arr = { 3, 4, 0, 1, 5 }
bucket0 = {3,0} ; bucket1 = {4,1} bucket2 = { 5 }
sum = 13 ; sum %3 = 1
bucket1 is not empty - chose minimal from it (1), and remove it from the array.
result array = { 3, 4, 0, 5 } 
proceed to STEP 4 "as planned"
    Ich habe nicht vollständig erhalten, deine O(n^2) Ansatz. Sie sagte, dass Sie erst alle Möglichkeiten, um entfernen 1 Anzahl . Das ist in Ordnung . Aber was kommt danach ? Wie wird die überprüfung für Paare mir die Antwort geben ?
    Sie müssen entfernen höchstens 2 zahlen, wenn Sie nicht erreichen können eine Zahl durch 3 teilbar durch entfernen von 3 zahlen - Sie können nicht get it at all.
    Mit der obigen Beobachtung - können Sie sich einen O(n) Lösung. Ich habe es in einem edit.
    Super!!! Einfach und effizient ! Danke ! Your 's und Steve' s Antworten sind die gleichen .. Danke Nochmal !
    Zwei Punkte: Du kannst es in O(n) Zeit, und Sie müssen entfernen Sie höchstens einen Punkt (außer in Sonderfällen). Siehe unten meine Antwort.

    InformationsquelleAutor amit

  2. 5

    Gierig Wahl definitiv nicht funktioniert: prüfen Sie die eingestellte {5, 2, 1}. Sie würde entfernen Sie die 1 ersten, aber Sie sollten entfernen Sie die 2.

    Ich denke, Sie sollten arbeiten, die Summe der Reihe modulo 3, also entweder 0 (fertig), oder 1, oder 2 ist. Dann bist du auf der Suche entfernen Sie die minimale Teilmenge, deren Summe modulo 3 ist 1 oder 2.

    Ich denke, das ist ziemlich einfach, so dass keine wirkliche Notwendigkeit für die dynamische Programmierung. Tun Sie es durch das entfernen eine Zahl, mit der das Modul wenn möglich, ansonsten tun es, indem Sie die zwei zahlen, mit der anderen E-Modul. Sobald Sie wissen, wie viele zu entfernen, wählen Sie den kleinsten möglichen. Sie nie brauchen, um entfernen Sie die drei zahlen.

    Brauchen Sie nicht zu behandeln 0 speziell, obwohl wenn du gehst, das zu tun, dann kann man weiter reduzieren, das unter Berücksichtigung der im Schritt 3, wenn Sie vorübergehend entfernen Sie alle 0, 3, 6, 9.

    Setzen Sie alle zusammen, würde ich wahrscheinlich:

    • Sortieren Sie die Ziffern absteigend.
    • Berechnung des E-Modul. Wenn 0, sind wir fertig.
    • Versuchen, Sie zu entfernen eine Ziffer mit, dass E-Modul, ab dem Ende. Wenn Sie erfolgreich sind, sind wir fertig.
    • Entfernen Sie die beiden Ziffern mit negativen-,-E-Modul, ab dem Ende. Dies immer gelingt, so sind wir fertig.
    • Könnten wir Links mit einem leeren array ein (z.B. wenn die Eingabe 1, 1), in welchem Fall das problem war unmöglich. Ansonsten enthält das array die stellen.

    Zeit-Komplexität ist O(n) vorausgesetzt, dass Sie in einer Zählung, Sortierung in Schritt 1. Was Sie sicherlich können, da die Werte stellen.

    Super!!! Ihre und Amit die Lösung sind identisch. Vielen Dank für das tolle und doch einfache algo !
    Ja, ich Schreibe mir da amit war die Bearbeitung sein. Der einzige Unterschied ist, dass er teilt sich in drei Eimer von E-Modul, während ich bin ein Mathematiker, also kann ich nicht bis 3 zählen und ich lass Sie alle in einem array 😉

    InformationsquelleAutor Steve Jessop

  3. 1

    Was haltet Ihr von diesem:

    zuerst ein array Sortieren von Elementen nach Wert

    sum up all numbers
- if sum's remainder after division by 3 is equal to 0, just return the sorted
  array
- otherwise
    - if sum of remainders after division by 3 of all the numbers is smaller
      than the remainder of their sum, there is no solution
    - otherwise
        - if it's equal to 1, try to return the smallest number with remainder
          equal to 1, or if no such, try two smallest with remainder equal to 2,
          if no such two (I suppose it can happen), there's no solution
        - if it's equal to 2, try to return the smallest number with remainder
          equal to 2, or if no such, try two smallest with remainder equal to 1,
          if no such two, there's no solution

    zuerst sortiert ein array-Elemente durch den Rest der division durch 3 aufsteigend
    dann ist jede Teilmenge von gleich der Rest Sortieren nach Wert absteigend

    Super!!! Scheint alle 3 Lösungen sind die gleichen.. Einfach und Effizient !

    InformationsquelleAutor Krzysztof Jabłoński

  4. 1

    Erste, der dieses problem reduziert sich auf die Maximierung der Anzahl der Elemente so gewählt, dass Ihre Summe ist durch 3 teilbar.

    Trivial: Wählen Sie alle zahlen teilbar durch 3 (0,3,6,9).

    Le a werden die Elemente, lassen Sie 1 als Rest, b werden die Elemente verlassen, die 2 als Rest. Wenn (|a|-|b|)%3 0 ist, dann wählen Sie alle Elemente aus a und b. Wenn (|a|-|b|)%3 ist 1, wählen Sie alle Elemente aus b, und |a|-1 höchsten zahlen aus. Wenn der Rest 2, und wählen Sie dann alle zahlen aus a, und |b|-1 höchsten zahlen von b.

    Sobald Sie haben alle die zahlen, sortiert diese in umgekehrter Reihenfolge und verketten. das ist Ihre Antwort.

    Letztlich, wenn n die Anzahl der Elemente in diesem Algorithmus gibt eine Zahl zurück, die al-least n-1 Ziffern lang sein (außer in Ausnahmefällen. siehe unten).

    HINWEIS: achten Sie darauf, von Sonderfällen(d.h. was ist |a|=0 oder |b|=0 etc). (-1)%3 = 2 und (-2)%3 = 1 .

    Wenn m ist die Größe des Alphabets, und n ist die Anzahl der Elemente, die mein Algorithmus ist O(m+n)

    InformationsquelleAutor ElKamina

  5. 0

    Sortierung der Daten ist unnötig, da es nur zehn verschiedene Werte.
    Nur die Anzahl der Nullen, Einsen, Zweien usw.. in O (n), wenn n zahlen gegeben sind.
    Berechnen Sie die Summe aller Ziffern, prüfen Sie, ob Sie den Rest modulo 3 ist 0, 1 oder 2.

    Wenn der Rest 1: Entfernen Sie den ersten der folgenden, die möglich ist (eine davon ist garantiert möglich): 1, 4, 7, 2+2, 2+5, 5+5, 2+8, 5+8, 8+8.

    Wenn der Rest 2: Entfernen Sie den ersten der folgenden, die möglich ist (eine davon ist garantiert möglich): 2, 5, 8, 1+1, 1+4, 4+4, 1+7, 4+7, 7+7.

    Wenn es keine Ziffern Links dann das problem nicht gelöst werden kann. Ansonsten, die Lösung entsteht durch die Verkettung von 9, 8, 7, und so weiter, so viele wie noch übrig sind.

    (Sortieren von n zahlen nehmen würde O (n log n). Es sei denn natürlich, die Sie Sortieren durch zählen, wie oft jede Ziffer vorkommt, und die Erzeugung der sortierten Folge nach diesen Nummern).

    InformationsquelleAutor gnasher729

  6. 0

    Amit die Antwort hat eine kleine Sache fehlt.

    Wenn bucket1 ist nicht leer, sondern es ist ein gigantischer Wert, sagen wir, 79 und 97 und b2 nicht leer ist, so gut und seine 2 minimals sind, sagen wir 2 und 5. Dann in diesem Fall, wenn der modulus der Summe aller Ziffern 1, wir wählen sollten, zu entfernen, 2 und 5 aus Eimer 2 anstelle des minimal-Eimer 1, um die größte verkettete Reihe.

    Testfall : 8 2 3 5 78 79

    Wenn wir Folgen Amits und Steve vorgeschlagene Methode, die größte Zahl wäre 878532 in der Erwägung, dass die größte Anzahl möglich divisble von 3 in diesem array ist 879783

    Lösung wäre ein Vergleich der entsprechenden Eimer kleinste minimal mit der Verkettung der beiden die minimals von den anderen Eimer und beseitigen Sie die kleinere.

    InformationsquelleAutor Awijit Gupta

Schreibe einen Kommentar