Étant donné un tableau d'entiers, de trouver le PLUS grand nombre en utilisant les chiffres du tableau tel qu'il est divisible par 3

E. g.: Tableau: 4,3,0,1,5 {Assumer tous les chiffres sont >=0. Aussi chaque élément dans le tableau correspondent à un chiffre. c'est à dire que chaque élément de la matrice est entre 0 et 9. }

Dans le tableau ci-dessus, le plus grand nombre est: 5430 {l'aide de chiffres 5, 4, 3 et 0 du tableau}

Mon Approche:

De divisibilité par 3, nous avons besoin de la somme des chiffres soit divisible par 3.
Donc,

  1. Étape 1: Supprimer tous les zéros de la matrice.
  2. Étape 2: Ces zéros à la fin. {Car ils ne pas affecter la somme, et nous devons trouver le plus grand nombre}
  3. Étape 3: Trouver le sous-ensemble des éléments du tableau (à l'exclusion des zéros) de telle sorte que le nombre de chiffres est MAXIMALE et que la somme des chiffres est MAXIMUM et la somme est divisible par 3.
  4. ÉTAPE 4: La chiffre comprend les chiffres ci-dessus trouvés dans l'ordre décroissant.

La principale étape est l'ÉTAPE 3 c'est à dire Comment trouver le sous-ensemble contient un MAXIMUM d'éléments tels que leur somme est MAX et est divisible par 3 .

Je pensais, peut-être les 3 pourrait être fait par le GOURMAND CHOIX de prendre tous les éléments et de les garder sur le retrait le plus petit élément dans le jeu jusqu'à la somme est divisible par 3.

Mais je ne suis pas convaincu que ce GOURMAND choix de travail.

Veuillez dire si ma démarche est correcte.
Si c'est le cas, veuillez indiquer comment faire, Étape 3 ?

Aussi, s'il vous plaît suggérer d'autres possibilités/algorithme efficace.

Ce que sur la force brute la production de toutes les possibilités ? C'est generatif toutes les combinaisons qui sont divisibles par 3, puis prendre le plus grand ?
l'étape 3 est un peu semblable, subset-sum problème, mais il sent aussi plus facile (il pourrait donc être solveable polynomialement après tout). Mais je doute gourmande va travailler ici.
Oui, la Force Brute est toujours une option. Mais j'ai été hinking si elle pouvait être fait d'une manière efficace.
Si nous utilisons subset-sum approche, alors nous aurons à examiner tous les multiples de 3: 3, 2*3, 3*3, 4*3 .. et ainsi de suite... Donc je suppose que deviendrait alors l'exponentielle.
Voici mon idée : Vous supprimer les zéros, ils seront ajoutés à la fin comme vous l'avez dit. N non nul chiffres Vous reste alors générer toutes les possibilités avec le maximum de longueur N. si vous trouvez quelque chose, vous prenez la valeur maximale. Peut-être trier les chiffres dans l'ordre décroissant peut être plus rapide. Si vous ne trouvez pas quelque chose, vous recherchez toutes les possibilités de longueur N-1, et ainsi de suite jusqu'à ce que vous trouver quelque chose.

OriginalL'auteur user1599964 | 2012-09-19

  1. 17

    Observation: Si vous pouvez obtenir un nombre qui est divisible par 3, vous devez supprimer au plus 2 chiffres, afin de maintenir la solution optimale.

    Un simple O(n^2) solution sera de vérifier toutes les possibilités de supprimer le 1 numéro, et si aucun n'est valide, vérifiez toutes les paires (Il y a O(n^2) de celles-ci).

    EDIT:

    O(n) solution: Créer 3 seaux - bucket1, bucket2, bucket0. Chaque désigne le module 3 de la valeur des nombres. Ignorer bucket0 dans l'algorithme suivant.

    Laisser la somme de la matrice être 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

    Remarque: Vous n'avez pas réellement besoin d'un seau, pour atteindre O(1) l'espace), vous devez seulement les 2 valeurs minimales de bucket1 et bucket2, puisque c'est le nombre que nous avons en fait utilisé à partir de ces seaux.

    Exemple:

    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"
    Je n'ai pas tout à fait obtenir votre O(n^2) approche. Vous avez dit d'abord de vérifier toutes les possibilités pour supprimer 1 nombre . C'est très bien . Mais ce qui est après que ? Comment vérifier paires de me donner la réponse ?
    Vous devez supprimer au plus 2 chiffres, si vous ne pouvez pas atteindre un nombre divisible par 3, par la suppression de 3 numéros - vous ne pouvez pas accéder à tous les.
    À l'aide de l'observation ci-dessus, vous pouvez obtenir un O(n) solution. Je l'ai ajouté dans un montage.
    Super ! Simple et efficace ! Merci ! Votre de et Steve réponses sont les mêmes .. Merci Encore !
    Deux points: Vous pouvez le faire en O(n) fois, et vous devez retirer au plus un point (sauf en cas de coin). Voir ci-dessous ma réponse.

    OriginalL'auteur amit

  2. 5

    Gourmand choix certainement ne fonctionne pas: considérer l'ensemble {5, 2, 1}. Il fallait retirer la 1 premier, mais vous devez supprimer le 2.

    Je pense que vous devriez travailler sur la somme de la gamme modulo 3, qui est soit 0 (vous avez fini), ou 1, ou 2. Alors vous êtes à la recherche pour retirer le sous-ensemble minimal dont la somme modulo 3 est 1 ou 2.

    Je pense que c'est assez simple, donc pas de réel besoin pour la programmation dynamique. Le faire en retirant un nombre avec ce module, si possible, sinon le faire en retirant les deux numéros avec l'autre module. Une fois que vous savez combien de supprimer, choisissez la plus petite possible. Vous n'aurez jamais besoin de retirer les trois numéros.

    Vous n'avez pas besoin de traiter 0 spécialement, mais si vous allez faire cela, alors vous pouvez réduire encore plus le jeu, en vertu de l'examen à l'étape 3 si vous supprimez temporairement tous les 0, 3, 6, 9.

    Mettre tous ensemble, je serais probablement:

    • Trier les chiffres, dans l'ordre décroissant.
    • Calculer le module. Si 0, nous avons fini.
    • Essayez de supprimer un chiffre avec ce module, à partir de la fin. En cas de succès, nous sommes finis.
    • Retirez les deux chiffres négatifs-qui-module, à partir de la fin. Cela réussit toujours, nous sommes finis.
    • On pourrait se retrouver avec un tableau vide (par exemple, si l'entrée est 1, 1), dans lequel cas, le problème était impossible. Sinon, le tableau contient les chiffres de notre résultat.

    Complexité temporelle est O(n) à condition de procéder à un comptage de tri à l'étape 1. Qui vous pouvez certainement puisque les valeurs sont des chiffres.

    Super ! Votre et Amit la solution sont identiques. Merci pour la grande et simple algo !
    Oui, j'ai écrit le mien comme il était l'édition de son. La seule différence est qu'il divise en trois catégories par module, alors que je suis mathématicien, donc je ne peux pas compter jusqu'à 3 et je viens de les laisser tous dans un tableau 😉

    OriginalL'auteur Steve Jessop

  3. 1

    Que pensez-vous de ceci:

    premier tri d'un tableau d'éléments de valeur

    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

    premier tri d'un tableau d'éléments par le reste de la division par 3 ascendant
    ensuite, chaque sous-ensemble de l'égalité reste trier les valeurs par ordre décroissant

    Super ! Paraît tous les 3 solutions sont les mêmes.. Simple et Efficace !

    OriginalL'auteur Krzysztof Jabłoński

  4. 1

    Tout d'abord, ce problème se réduit à maximiser le nombre d'éléments sélectionnés de telle sorte que leur somme est divisible par 3.

    Trivial: Sélectionnez tous les nombres divisibles par 3 (0,3,6,9).

    Le un les éléments de laisser 1 comme reste, b les éléments de congé de 2, comme le reste. Si (|a|-|b|)%3 est 0, puis sélectionnez tous les éléments de a et de b. Si (|a|-|b|)%3 est 1, sélectionnez tous les éléments de b, et |a|-1 nombre le plus élevé d'un. Si le reste est 2, puis sélectionnez tous les nombres de un, et de |b|-1 nombre le plus élevé de b.

    Une fois que vous avez tous les nombres, de les trier dans l'ordre inverse et de les concaténer. c'est votre réponse.

    En définitive, si n est le nombre d'éléments de cet algorithme renvoie un nombre qui est al moins n-1 chiffres (à l'exception des cas limites. voir ci-dessous).

    REMARQUE: Prenez soin de cas du coin(c'est à dire qu'est-ce que |a|=0 ou |b|=0, etc). (-1)%3 = 2 et (-2)%3 = 1 .

    Si m est la taille de l'alphabet, et n est le nombre d'éléments, c'est mon algorithme est O(m+n)

    OriginalL'auteur ElKamina

  5. 0

    Tri des données est inutile, car il y a seulement une dizaine de valeurs différentes.
    Juste compter le nombre de zéros, ceux d'un, de deux, etc. en O (n) si n chiffres sont donnés.
    Calculer la somme de tous les chiffres, vérifiez si le reste modulo 3 est 0, 1 ou 2.

    Si le reste est de 1: Supprimer le premier de la suivante qui est possible (l'un de ces est la garantie d'être possible): 1, 4, 7, 2+2, 2+5, 5+5, 2+8, 5+8, 8+8.

    Si le reste est 2: Supprimer le premier de la suivante qui est possible (l'un de ces est la garantie d'être possible): 2, 5, 8, 1+1, 1+4, 4+4, 1+7, 4+7, 7+7.

    Si il n'existe pas de chiffres à gauche puis le problème ne peut être résolu. Sinon, la solution est créé en concaténant les 9, 8, 7, et ainsi de sur.

    (Tri de n chiffres prendrait O (n log n). Sauf si bien sûr vous de tri par comptage du nombre de fois chaque chiffre se produit et à la production des résultats triés selon ces chiffres).

    OriginalL'auteur gnasher729

  6. 0

    Amit, en réponse a une petite chose qui manque.

    Si bucket1 n'est pas vide, mais il a une énorme valeur, disons 79 et 97 et b2 n'est pas vide et ses 2 minimals sont, disons 2 et 5. Alors dans ce cas, lorsque le module de la somme de tous les chiffres de 1, nous devrions choisir de supprimer 2 et 5 de seau de 2 au lieu du minimum dans un seau 1 pour obtenir le plus grand nombre concaténé.

    Cas de Test : 8 2 3 5 78 79

    Si nous suivons Amits et Steve méthode proposée, le plus grand nombre serait 878532 alors que le plus grand nombre possible divisble par 3 dans ce tableau est 879783

    Solution serait de comparer le approprié seau le plus petit avec un minimum de la concaténation des deux minimals de l'autre seau et d'éliminer les petits.

    OriginalL'auteur Awijit Gupta