La question d'entretien facile est devenue plus difficile: étant donné les nombres 1 à 100, trouvez le ou les nombres manquants donnés exactement k sont manquants

J'ai eu une expérience d'embauche intéressante il y a quelque temps. La question a commencé très facilement:

Q1 : Nous avons un sac contenant des nombres 1, 2, 3, ..., 100. Chaque numéro apparaît exactement une fois, il y a donc 100 numéros. Maintenant, un numéro est choisi au hasard dans le sac. Trouvez le numéro manquant.

J'ai entendu cette question d'entrevue avant, bien sûr, alors j'ai répondu très rapidement dans le sens de:

A1 : Eh bien, la somme des nombres 1 + 2 + 3 + … + Nest (N+1)(N/2)(voir Wikipedia: somme des séries arithmétiques ). Car N = 100, la somme est 5050.

Ainsi, si tous les numéros sont présents dans le sac, la somme sera exactement 5050. Puisqu'un nombre est manquant, la somme sera inférieure à cela et la différence est ce nombre. Nous pouvons donc trouver ce nombre manquant dans le O(N)temps et l' O(1)espace.

À ce stade, je pensais avoir bien fait, mais tout d'un coup, la question a pris une tournure inattendue:

Q2 : C'est exact, mais maintenant comment feriez-vous si DEUX numéros sont manquants?

Je n'avais jamais vu / entendu / envisagé cette variation auparavant, alors j'ai paniqué et je n'ai pas pu répondre à la question. L'intervieweur a insisté pour connaître mon processus de réflexion, j'ai donc mentionné que nous pourrions peut-être obtenir plus d'informations en comparant avec le produit attendu, ou peut-être faire un deuxième passage après avoir recueilli des informations lors du premier passage, etc., mais je ne faisais que tirer dans l'obscurité plutôt que d'avoir réellement un chemin clair vers la solution.

L'enquêteur a essayé de m'encourager en disant qu'avoir une deuxième équation est en effet une façon de résoudre le problème. À ce stade, j'étais un peu contrarié (de ne pas avoir connu la réponse à l'avance) et j'ai demandé s'il s'agissait d'une technique de programmation générale (lire: "utile"), ou s'il s'agissait simplement d'une réponse astucieuse.

La réponse de l'intervieweur m'a surpris: vous pouvez généraliser la technique pour trouver 3 nombres manquants. En fait, vous pouvez le généraliser pour trouver k nombres manquants.

Qk : Si exactement k nombres manquent dans le sac, comment le trouveriez-vous efficacement?

C'était il y a quelques mois, et je n'arrivais toujours pas à comprendre quelle était cette technique. De toute évidence , il y a une Ω(N)limite de temps inférieure puisque nous devons analyser tous les chiffres au moins une fois, mais l'intervieweur a insisté pour que le TIME et SPACE complexité de la technique de résolution (moins le O(N)balayage d'entrée de temps) est défini dans k pas N .

La question ici est donc simple:

• Comment résoudriez-vous Q2 ?
• Comment résoudriez-vous Q3 ?
• Comment résoudriez- vous Qk ?

Clarifications

• Généralement, il y a N nombres de 1 .. N , pas seulement 1..100.
• Je ne cherche pas la solution évidente basée sur un ensemble , par exemple en utilisant un ensemble de bits , en codant la présence / absence de chaque nombre par la valeur d'un bit désigné, donc en utilisant des O(N)bits dans un espace supplémentaire. Nous ne pouvons pas d'espace supplémentaire proportionnel à N .
• Je ne recherche pas non plus l'approche évidente du tri en premier. Cela et l'approche basée sur les ensembles méritent d'être mentionnés dans une interview (ils sont faciles à mettre en œuvre et, selon N , peuvent être très pratiques). Je recherche la solution Holy Graal (qui peut ou non être pratique à mettre en œuvre, mais qui a néanmoins les caractéristiques asymptotiques souhaitées).

Encore une fois, bien sûr, vous devez scanner l'entrée O(N), mais vous ne pouvez capturer qu'une petite quantité d'informations (définies en termes de k et non de N ), et devez ensuite trouver les k nombres manquants d'une manière ou d'une autre.

Voici un résumé du lien de Dimitris Andreou .

Rappelez-vous la somme des puissances i-ème, où i = 1,2, .., k. Cela réduit le problème de la résolution du système d'équations

a ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

En utilisant les identités de Newton , connaître b _i permet de calculer

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ + a ₁ a ₃ + ... + a _k-1 a _k

...

c _k = a ₁ a ₂ ... a _k

Si vous développez le polynôme (xa ₁ ) ... (xa _k ) les coefficients seront exactement c ₁ , ..., c _k - voir les formules de Viète . Étant donné que tous les facteurs polynomiaux sont uniques (l'anneau de polynômes est un domaine euclidien ), cela signifie que les _i sont déterminés de manière unique, jusqu'à la permutation.

Cela met fin à une preuve que se souvenir des pouvoirs est suffisant pour récupérer les chiffres. Pour k constant, c'est une bonne approche.

Cependant, lorsque k varie, l'approche directe du calcul de c ₁ , ..., c _k est d'un coût prohibitif, car par exemple c _k est le produit de tous les nombres manquants, magnitude n! / (Nk) !. Pour surmonter cela, effectuez des calculs dans le champ Z _q , où q est un nombre premier tel que n <= q <2n - il existe par le postulat de Bertrand . La preuve n'a pas besoin d'être modifiée, car les formules sont toujours valables et la factorisation des polynômes est toujours unique. Vous avez également besoin d'un algorithme de factorisation sur des champs finis, par exemple celui de Berlekamp ou Cantor-Zassenhaus .

Pseudocode de haut niveau pour k constant:

• Calculer les puissances i-ème de nombres donnés
• Soustrayez pour obtenir des sommes de i-ème pouvoirs de nombres inconnus. Appelez les sommes b _i .
• Utilisez les identités de Newton pour calculer les coefficients à partir de b _i ; appelez-les c _i . Fondamentalement, c ₁ = b ₁ ; c ₂ = (c ₁ b ₁ - b ₂ ) / 2; voir Wikipedia pour les formules exactes
• Factoriser le polynôme x ^k -c ₁ x ^k-1 + ... + c _k .
• Les racines du polynôme sont les nombres nécessaires a ₁ , ..., a _k .

Pour faire varier k, trouver un premier n <= q <2n en utilisant par exemple Miller-Rabin, et effectuer les étapes avec tous les nombres réduits modulo q.

EDIT: La version précédente de cette réponse indiquait qu'au lieu de Z _q , où q est premier, il est possible d'utiliser un champ fini de caractéristique 2 (q = 2 ^ (log n)). Ce n'est pas le cas, car les formules de Newton nécessitent une division par des nombres jusqu'à k.

Vous le trouverez en lisant les quelques pages de Muthukrishnan - Algorithmes de flux de données: Puzzle 1: Trouver les nombres manquants . Il montre exactement la généralisation que vous recherchez . C'est probablement ce que votre intervieweur a lu et pourquoi il a posé ces questions.

Maintenant, si seulement les gens commençaient à supprimer les réponses qui sont subsumées ou remplacées par le traitement de Muthukrishnan, et rendraient ce texte plus facile à trouver. :)

Voir également la réponse directement liée de sdcvvc , qui comprend également le pseudocode (hourra! Pas besoin de lire ces formulations mathématiques difficiles :)) (merci, excellent travail!).

Nous pouvons résoudre Q2 en additionnant à la fois les nombres eux-mêmes et les carrés des nombres.

Nous pouvons alors réduire le problème à

k1 + k2 = x
k1^2 + k2^2 = y

Où xet dans yquelle mesure les sommes sont inférieures aux valeurs attendues.

La substitution nous donne:

(x-k2)^2 + k2^2 = y

Que nous pouvons ensuite résoudre pour déterminer nos numéros manquants.

Comme l'a souligné @j_random_hacker, cela est assez similaire à la recherche de doublons dans le temps O (n) et l'espace O (1) , et une adaptation de ma réponse y fonctionne également ici.

En supposant que le "sac" est représenté par un tableau A[]de taille basé sur 1 N - k, nous pouvons résoudre Qk dans le O(N)temps etO(k) espace supplémentaire.

Tout d'abord, nous étendons notre tableau A[]par kéléments, afin qu'il soit maintenant de taille N. Ceci est l' O(k)espace supplémentaire. Nous exécutons ensuite l'algorithme de pseudo-code suivant:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

La première boucle initialise les kentrées supplémentaires de la même manière que la première entrée du tableau (c'est juste une valeur pratique que nous savons déjà présente dans le tableau - après cette étape, toutes les entrées manquantes dans le tableau de taille initialN-k sont toujours manquant dans le tableau étendu).

La deuxième boucle permute le tableau étendu de sorte que si l'élément xest présent au moins une fois, alors l'une de ces entrées sera en positionA[x] .

Notez que bien qu'il ait une boucle imbriquée, il fonctionne toujours en O(N)temps - un swap ne se produit que s'il y a une itelle que A[i] != i, et chaque jeux de swap au moins un élément tel que A[i] == i, lorsque cela n'a pas été vrai avant. Cela signifie que le nombre total de swaps (et donc le nombre total d'exécutions du whilecorps de boucle) est au maximum N-1.

La troisième boucle affiche les index du tableau iqui ne sont pas occupés par la valeur i- cela signifie qu'ils idoivent avoir été manquants.

J'ai demandé à un enfant de 4 ans de résoudre ce problème. Il tria les chiffres puis compta. Cela a un espace requis de O (sol de la cuisine), et cela fonctionne tout aussi facilement, mais il manque de nombreuses boules.

Je ne sais pas si c'est la solution la plus efficace, mais je ferais une boucle sur toutes les entrées et utiliserais un ensemble de bits pour me souvenir, quels nombres sont définis, puis je testerais 0 bit.

J'aime les solutions simples - et je crois même que cela pourrait être plus rapide que de calculer la somme, ou la somme des carrés, etc.

Je n'ai pas vérifié les calculs, mais je soupçonne que le calcul Σ(n^2)dans la même passe que nous calculons Σ(n)fournirait suffisamment d'informations pour obtenir deux nombres manquants, faites Σ(n^3)aussi s'il y en a trois, et ainsi de suite.

Le problème avec les solutions basées sur des sommes de nombres est qu'elles ne prennent pas en compte le coût de stockage et de travail avec des nombres avec de grands exposants ... en pratique, pour que cela fonctionne pour de très grands n, une grande bibliothèque de nombres serait utilisée . Nous pouvons analyser l'utilisation de l'espace pour ces algorithmes.

Nous pouvons analyser la complexité temporelle et spatiale des algorithmes sdcvvc et Dimitris Andreou.

Espace de rangement:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Donc l_j \in \Theta(j log n)

Stockage total utilisé: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Espace utilisé: en supposant que le calcul a^jprenne du ceil(log_2 j)temps, temps total:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Temps total utilisé: \Theta(kn log n)

Si ce temps et cet espace sont satisfaisants, vous pouvez utiliser un algorithme récursif simple. Soit b! I la ième entrée dans le sac, n le nombre de nombres avant les suppressions et k le nombre de suppressions. Dans la syntaxe Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Stockage utilisé: O(k)pour la liste, O(log(n))pour la pile: O(k + log(n)) cet algorithme est plus intuitif, a la même complexité temporelle et utilise moins d'espace.

Attends une minute. Comme la question est posée, il y a 100 numéros dans le sac. Quelle que soit la taille de k, le problème peut être résolu en temps constant car vous pouvez utiliser un ensemble et supprimer des nombres de l'ensemble en 100 itérations au plus d'une boucle. 100 est constant. L'ensemble des nombres restants est votre réponse.

Si nous généralisons la solution aux nombres de 1 à N, rien ne change sauf que N n'est pas une constante, donc nous sommes en O (N - k) = O (N) temps. Par exemple, si nous utilisons un ensemble de bits, nous définissons les bits à 1 dans le temps O (N), parcourons les nombres, en mettant les bits à 0 au fur et à mesure (O (Nk) = O (N)), puis nous avoir la réponse.

Il me semble que l'intervieweur vous demandait comment imprimer le contenu de l'ensemble final en temps O (k) plutôt qu'en temps O (N). De toute évidence, avec un bit défini, vous devez parcourir tous les N bits pour déterminer si vous devez imprimer le nombre ou non. Cependant, si vous modifiez la façon dont l'ensemble est implémenté, vous pouvez imprimer les nombres en k itérations. Cela se fait en plaçant les nombres dans un objet à stocker à la fois dans un ensemble de hachage et dans une liste doublement liée. Lorsque vous supprimez un objet de l'ensemble de hachage, vous le supprimez également de la liste. Les réponses seront laissées dans la liste qui est maintenant de longueur k.

Pour résoudre la question des 2 (et 3) nombres manquants, vous pouvez modifier quickselect, qui s'exécute en moyenne O(n)et utilise une mémoire constante si le partitionnement est effectué sur place.

1. Partitionnez l'ensemble par rapport à un pivot aléatoire pen partitions l, qui contiennent des nombres inférieurs au pivot, et r, qui contiennent des nombres supérieurs au pivot.

2. Déterminez dans quelles partitions se trouvent les 2 nombres manquants en comparant la valeur pivot à la taille de chaque partition ( p - 1 - count(l) = count of missing numbers in let n - count(r) - p = count of missing numbers in r)

3. a) S'il manque un numéro à chaque partition, utilisez l'approche de la différence des sommes pour trouver chaque numéro manquant.

   (1 + 2 + ... + (p-1)) - sum(l) = missing #1 et ((p+1) + (p+2) ... + n) - sum(r) = missing #2

   b) Si une partition manque les deux numéros et la partition est vide, alors les numéros manquants sont soit (p-1,p-2)ou (p+1,p+2) selon la partition qui manque les numéros.

   Si une partition manque de 2 numéros mais n'est pas vide, alors récursivement sur cette partition.

Avec seulement 2 nombres manquants, cet algorithme supprime toujours au moins une partition, de sorte qu'il conserve O(n)la complexité temporelle moyenne de la sélection rapide. De même, avec 3 numéros manquants, cet algorithme supprime également au moins une partition à chaque passage (car comme avec 2 numéros manquants, au plus une seule partition contiendra plusieurs numéros manquants). Cependant, je ne sais pas combien les performances diminuent lorsque davantage de nombres manquants sont ajoutés.

Voici une implémentation qui n'utilise pas de partitionnement sur place, donc cet exemple ne répond pas à l'espace requis mais il illustre les étapes de l'algorithme:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Démo

Voici une solution qui utilise k bits de stockage supplémentaire, sans astuces intelligentes et simplement. Temps d'exécution O (n), espace supplémentaire O (k). Juste pour prouver que cela peut être résolu sans lire d'abord la solution ou être un génie:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

Pouvez-vous vérifier si chaque numéro existe? Si oui, vous pouvez essayer ceci:

S = somme de tous les nombres dans le sac (S <5050)
Z = somme des nombres manquants 5050 - S

si les nombres manquants le sont x, ypuis:

x = Z - y et
max (x) = Z - 1

Vous vérifiez donc la plage de 1à max(x)et trouvez le nombre

Peut-être que cet algorithme peut fonctionner pour la question 1:

1. Précalculer le xor des 100 premiers entiers (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
2. xou les éléments car ils continuent de provenir du flux d'entrée (val1 = val1 ^ next_input)
3. réponse finale = val ^ val1

Ou encore mieux:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

Cet algorithme peut en effet être étendu pour deux nombres manquants. La première étape reste la même. Lorsque nous appelons GetValue avec deux nombres manquants, le résultat sera un a1^a2sont les deux nombres manquants. Disons

val = a1^a2

Maintenant, pour filtrer a1 et a2 de val, nous prenons n'importe quel bit défini dans val. Disons que le ithbit est défini sur val. Cela signifie que a1 et a2 ont une parité différente à la ithposition du bit. Maintenant, nous faisons une autre itération sur le tableau d'origine et gardons deux valeurs xor. Un pour les nombres qui ont le ième bit et l'autre qui n'a pas le ième bit. Nous avons maintenant deux seaux de nombres, et sa garantie a1 and a2se trouvera dans différents seaux. Maintenant, répétez la même chose que nous avons fait pour trouver un élément manquant sur chacun des seaux.

Vous pouvez résoudre Q2 si vous avez la somme des deux listes et le produit des deux listes.

(l1 est l'original, l2 est la liste modifiée)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Nous pouvons l'optimiser car la somme d'une série arithmétique est n fois la moyenne des premier et dernier termes:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Maintenant, nous savons que (si a et b sont les nombres supprimés):

a + b = d
a * b = m

Ainsi, nous pouvons réorganiser pour:

a = s - b
b * (s - b) = m

Et multipliez:

-b^2 + s*b = m

Et réorganisez pour que le côté droit soit nul:

-b^2 + s*b - m = 0

Ensuite, nous pouvons résoudre avec la formule quadratique:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Exemple de code Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Je ne connais pas la complexité des fonctions sqrt, reduction et sum, je ne peux donc pas calculer la complexité de cette solution (si quelqu'un le sait, veuillez commenter ci-dessous.)

Pour Q2, c'est une solution qui est un peu plus inefficace que les autres, mais qui a toujours le temps d'exécution O (N) et prend de l'espace O (k).

L'idée est d'exécuter l'algorithme d'origine deux fois. Dans le premier, vous obtenez un nombre total qui est manquant, ce qui vous donne une limite supérieure des nombres manquants. Appelons ce numéro N. Vous savez que les deux nombres manquants vont résumer N, donc le premier nombre ne peut être que dans l'intervalle [1, floor((N-1)/2)]tandis que le second va être [floor(N/2)+1,N-1].

Ainsi, vous bouclez à nouveau sur tous les numéros, en rejetant tous les numéros qui ne sont pas inclus dans le premier intervalle. Ceux qui le sont, vous gardez une trace de leur somme. Enfin, vous connaîtrez l'un des deux numéros manquants et, par extension, le second.

J'ai le sentiment que cette méthode pourrait être généralisée et peut-être plusieurs recherches exécutées en "parallèle" lors d'un seul passage sur l'entrée, mais je n'ai pas encore compris comment.

Je pense que cela peut se faire sans équations et théories mathématiques complexes. Vous trouverez ci-dessous une proposition de solution de complexité en place et O (2n):

Hypothèses du formulaire d'entrée:

Nombre de numéros dans le sac = n

Nombre de nombres manquants = k

Les nombres dans le sac sont représentés par un tableau de longueur n

Longueur du tableau d'entrée pour l'algo = n

Les entrées manquantes dans le tableau (nombres sortis du sac) sont remplacées par la valeur du premier élément du tableau.

Par exemple. Au départ, le sac ressemble à [2,9,3,7,8,6,4,5,1,10]. Si 4 est retiré, la valeur de 4 deviendra 2 (le premier élément du tableau). Par conséquent, après avoir retiré 4 le sac ressemblera à [2,9,3,7,8,6,2,5,1,10]

La clé de cette solution consiste à baliser l'INDEX d'un nombre visité en annulant la valeur à cet INDEX lorsque le tableau est parcouru.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

Il existe un moyen général de généraliser des algorithmes de streaming comme celui-ci. L'idée est d'utiliser un peu de randomisation pour, espérons-le, «répartir» les kéléments en sous-problèmes indépendants, où notre algorithme d'origine résout le problème pour nous. Cette technique est utilisée, entre autres, dans la reconstruction de signaux clairsemés.

• Créez un tableau ade taille u = k^2.
• Choisissez une fonction de hachage universelle , h : {1,...,n} -> {1,...,u}. (Comme multiplier-shift )
• Pour chacun ien 1, ..., naugmentationa[h(i)] += i
• Pour chaque numéro xdu flux d'entrée, décrémentez a[h(x)] -= x.

Si tous les nombres manquants ont été hachés dans des compartiments différents, les éléments non nuls du tableau contiendront désormais les nombres manquants.

La probabilité qu'une paire particulière soit envoyée au même compartiment, est moindre que 1/upar définition d'une fonction de hachage universelle. Puisqu'il y a environ des k^2/2paires, nous avons que la probabilité d'erreur est au plus k^2/2/u=1/2. Autrement dit, nous réussissons avec une probabilité d'au moins 50%, et si nous augmentonsu nous augmentons nos chances.

Notez que cet algorithme prend des k^2 lognbits d'espace (nous avons besoin de lognbits par compartiment de tableau.) Cela correspond à l'espace requis par la réponse de @Dimitris Andreou (en particulier l'exigence d'espace de factorisation polynomiale, qui se trouve également être randomisée.) Cet algorithme a également une constante le temps par mise à jour, plutôt que le temps kdans le cas des sommes de puissance.

En fait, nous pouvons être encore plus efficaces que la méthode de la somme de puissance en utilisant l'astuce décrite dans les commentaires.

Une solution très simple au Q2 à laquelle je suis surpris, personne n'a déjà répondu. Utilisez la méthode du T1 pour trouver la somme des deux nombres manquants. Notons-le par S, alors l'un des nombres manquants est plus petit que S / 2 et l'autre plus grand que S / 2 (duh). Additionnez tous les nombres de 1 à S / 2 et comparez-le au résultat de la formule (de manière similaire à la méthode du premier trimestre) pour trouver le plus bas entre les nombres manquants. Soustrayez-le de S pour trouver le plus grand nombre manquant.

Très beau problème. Je choisirais d'utiliser une différence définie pour Qk. De nombreux langages de programmation sont même pris en charge, comme dans Ruby:

missing = (1..100).to_a - bag

Ce n'est probablement pas la solution la plus efficace mais c'est celle que j'utiliserais dans la vraie vie si j'étais confronté à une telle tâche dans ce cas (limites connues, limites basses). Si l'ensemble de nombres était très grand, je considérerais un algorithme plus efficace, bien sûr, mais jusque-là, la solution simple me suffirait.

Vous pouvez essayer d'utiliser un filtre Bloom . Insérez chaque numéro dans le sac dans la fleur, puis répétez sur l'ensemble complet de 1 k jusqu'à ce que chacun ne soit pas trouvé. Cela peut ne pas trouver la réponse dans tous les scénarios, mais peut être une bonne solution.

Je prendrais une approche différente de cette question et sonderais l'intervieweur pour plus de détails sur le problème plus vaste qu'il essaie de résoudre. Selon le problème et les exigences qui l'entourent, la solution basée sur un ensemble évident pourrait être la bonne chose et l'approche générer-une-liste-et-choisir-après-pas.

Par exemple, il se peut que l'intervieweur envoie des nmessages et ait besoin de savoir ce kqui n'a pas donné lieu à une réponse et doit le savoir en un minimum de temps d'horloge murale après len-k arrivée de e réponse. Disons également que la nature du canal de message est telle que même en cours d'exécution, il y a suffisamment de temps pour effectuer un traitement entre les messages sans avoir d'impact sur le temps nécessaire pour produire le résultat final après l'arrivée de la dernière réponse. Ce temps peut être utilisé pour insérer une facette d'identification de chaque message envoyé dans un ensemble et le supprimer à mesure que chaque réponse correspondante arrive. Une fois la dernière réponse arrivée, la seule chose à faire est de supprimer son identifiant de l'ensemble, ce qui, dans les implémentations typiques, prendO(log k+1). Après cela, l'ensemble contient la liste des kéléments manquants et aucun traitement supplémentaire n'est à effectuer.

Ce n'est certainement pas l'approche la plus rapide pour le traitement par lots de sacs de nombres pré-générés car tout fonctionne O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Mais cela fonctionne pour n'importe quelle valeur de k(même si elle n'est pas connue à l'avance) et dans l'exemple ci-dessus, elle a été appliquée de manière à minimiser l'intervalle le plus critique.

Vous pouvez motiver la solution en y réfléchissant en termes de symétries (groupes, en langage mathématique). Peu importe l'ordre de l'ensemble des nombres, la réponse doit être la même. Si vous allez utiliser des kfonctions pour aider à déterminer les éléments manquants, vous devriez penser aux fonctions qui ont cette propriété: symétrique. La fonction s_1(x) = x_1 + x_2 + ... + x_nest un exemple de fonction symétrique, mais il y en a d'autres de degré supérieur. En particulier, considérons les fonctions symétriques élémentaires . La fonction symétrique élémentaire du degré 2 est s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_nla somme de tous les produits de deux éléments. De même pour les fonctions élémentaires symétriques de degré 3 et supérieur. Ils sont évidemment symétriques. En outre, il s'avère que ce sont les éléments constitutifs de toutes les fonctions symétriques.

Vous pouvez construire les fonctions symétriques élémentaires au fur et à mesure en notant cela s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Une réflexion plus approfondie devrait vous convaincre de cela s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))et ainsi de suite, afin qu'ils puissent être calculés en un seul passage.

Comment savoir quels éléments manquaient dans le tableau? Pensez au polynôme (z-x_1)(z-x_2)...(z-x_n). Il évalue 0si vous entrez l'un des nombres x_i. L'élargissement du polynôme, vous obtenez z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Les fonctions symétriques élémentaires apparaissent ici aussi, ce qui n'est vraiment pas surprenant, car le polynôme devrait rester le même si nous appliquons une permutation aux racines.

Nous pouvons donc construire le polynôme et essayer de le factoriser pour déterminer quels nombres ne sont pas dans l'ensemble, comme d'autres l'ont mentionné.

Enfin, si nous sommes préoccupés par le débordement de la mémoire avec de grands nombres (le nième polynôme symétrique sera de l'ordre 100!), nous pouvons faire ces calculs mod poù pest un nombre premier supérieur à 100. Dans ce cas, nous évaluons le polynôme mod pet constatons qu'il évalue à nouveau à 0lorsque l'entrée est un nombre dans l'ensemble, et il évalue à une valeur non nulle lorsque l'entrée est un nombre non dans l'ensemble. Cependant, comme d'autres l'ont souligné, pour extraire les valeurs du polynôme dans le temps qui dépend k, non N, nous devons factoriser le polynôme mod p.

Encore une autre façon utilise le filtrage de graphe résiduel.

Supposons que nous ayons les numéros 1 à 4 et que 3 soit manquant. La représentation binaire est la suivante,

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

Et je peux créer un organigramme comme celui-ci.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

Notez que le graphe de flux contient x nœuds, tandis que x est le nombre de bits. Et le nombre maximum d'arêtes est (2 * x) -2.

Ainsi, pour un entier 32 bits, il faudra un espace O (32) ou O (1).

Maintenant, si je supprime la capacité de chaque nombre à partir de 1,2,4, il me reste un graphique résiduel.

0 ----------> 1 ---------> 1

Enfin, je vais exécuter une boucle comme la suivante,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Maintenant, le résultat est en resultcontient des nombres qui ne manquent pas également (faux positif). Mais le k <= (taille du résultat) <= n lorsqu'il kmanque des éléments.

Je vais parcourir la liste donnée une dernière fois pour marquer le résultat manquant ou non.

La complexité temporelle sera donc O (n).

Enfin, il est possible de réduire le nombre de faux positifs (et l'espace requis) en prenant des nœuds 00, 01, 11, au 10lieu de simplement 0et 1.

Vous auriez probablement besoin d'éclaircissements sur ce que signifie O (k).

Voici une solution triviale pour k arbitraire: pour chaque v de votre ensemble de nombres, accumulez la somme de 2 ^ v. À la fin, boucle i de 1 à N. Si la somme AND au niveau du bit avec 2 ^ i est nulle, alors i est manquant. (Ou numériquement, si le plancher de la somme divisée par 2 ^ i est pair. Ou sum modulo 2^(i+1)) < 2^i.)

Facile, non? O (N) temps, O (1) de stockage, et il prend en charge arbitraire k.

Sauf que vous calculez d'énormes nombres qui, sur un ordinateur réel, nécessiteraient chacun un espace O (N). En fait, cette solution est identique à un vecteur de bits.

Vous pourriez donc être intelligent et calculer la somme et la somme des carrés et la somme des cubes ... jusqu'à la somme de v ^ k, et faire le calcul de fantaisie pour extraire le résultat. Mais ce sont aussi de grands nombres, ce qui pose la question: de quel modèle de fonctionnement abstrait parlons-nous? Combien tient dans l'espace O (1) et combien de temps faut-il pour résumer les nombres de la taille dont vous avez besoin?

Voici une solution qui ne repose pas sur des mathématiques complexes comme le font les réponses de sdcvvc / Dimitris Andreou, ne change pas le tableau d'entrée comme l'ont fait caf et le colonel Panic, et n'utilise pas le jeu de bits de taille énorme comme Chris Lercher, JeremyP et beaucoup d'autres l'ont fait. Fondamentalement, j'ai commencé avec l'idée de Svalorzen / Gilad Deutch pour Q2, je l'ai généralisée au cas courant Qk et implémentée en Java pour prouver que l'algorithme fonctionne.

L'idée

Supposons que nous ayons un intervalle arbitraire I dont nous savons seulement qu'il contient au moins un des nombres manquants. Après un passage à travers le réseau d'entrée, ne regardant que les chiffres de I , on peut obtenir à la fois la somme S et la quantité Q de chiffres manquants I . Nous faisons cela en décrémentant simplement la longueur de I à chaque fois que nous rencontrons un nombre de I (pour obtenir Q ) et en diminuant la somme pré-calculée de tous les nombres de I par ce nombre rencontré à chaque fois (pour obtenir S ).

Maintenant , nous regardons S et Q . Si Q = 1 , cela signifie que alors je ne compte qu'un des numéros manquants, et ce nombre est clairement S . Nous marquons I comme terminé (il est appelé "sans ambiguïté" dans le programme) et le laissons de côté. D'autre part, si Q> 1 , on peut calculer la moyenne A = S / Q des nombres manquants contenus dans I . Comme tous les nombres sont distincts, au moins l' un de ces nombres est strictement inférieur à A et au moins un est strictement supérieur à un . Maintenant, nous avons divisé I en Aen deux intervalles plus petits dont chacun contient au moins un nombre manquant. Notez que peu importe à quels intervalles nous attribuons A au cas où il s'agit d'un entier.

Nous faisons la passe de tableau suivante calculant S et Q pour chacun des intervalles séparément (mais dans la même passe) et après cela, marquons les intervalles avec Q = 1 et divisons les intervalles avec Q> 1 . Nous continuons ce processus jusqu'à ce qu'il n'y ait pas de nouveaux intervalles "ambigus", c'est-à-dire que nous n'avons rien à diviser car chaque intervalle contient exactement un nombre manquant (et nous connaissons toujours ce nombre parce que nous connaissons S ). Nous partons du seul intervalle "plage entière" contenant tous les nombres possibles (comme [1..N] dans la question).

Analyse de la complexité du temps et de l'espace

Le nombre total de passes p que nous devons effectuer jusqu'à l'arrêt du processus n'est jamais supérieur au nombre manquant de k . L'inégalité p <= k peut être rigoureusement démontrée. D'autre part, il existe également une borne supérieure empirique p <log ₂ N + 3 qui est utile pour les grandes valeurs de k . Nous devons effectuer une recherche binaire pour chaque numéro du tableau d'entrée pour déterminer l'intervalle auquel il appartient. Cela ajoute le multiplicateur log k à la complexité temporelle.

Au total, la complexité temporelle est O (N ᛫ min (k, log N) ᛫ log k) . Notez que pour les grands k , c'est nettement mieux que celui de la méthode de sdcvvc / Dimitris Andreou, qui est O (N ᛫ k) .

Pour son travail, l'algorithme nécessite O (k) d' espace supplémentaire pour le stockage à la plupart des k intervalles, ce qui est nettement meilleur que O (N) dans les solutions de "bits".

Implémentation Java

Voici une classe Java qui implémente l'algorithme ci-dessus. Il renvoie toujours un tableau trié de nombres manquants. En plus de cela, il ne nécessite pas le nombre k manquant car il le calcule lors de la première passe. L'ensemble des nombres est donné par les paramètres minNumberet maxNumber(par exemple 1 et 100 pour le premier exemple de la question).

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

Par souci d'équité, cette classe reçoit des données sous forme d' NumberBagobjets. NumberBagne permet pas la modification du tableau et l'accès aléatoire et compte également le nombre de fois que le tableau a été demandé pour une traversée séquentielle. Il est également plus approprié pour les tests de grands tableaux que Iterable<Integer>parce qu'il évite la mise en boîte de intvaleurs primitives et permet d'envelopper une partie d'un grand int[]pour une préparation de test pratique. Il n'est pas difficile de remplacer, si vous le souhaitez, NumberBagpar int[]ou de Iterable<Integer>taper la findsignature, en y changeant deux boucles for en boucles foreach.

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

Les tests

Des exemples simples démontrant l'utilisation de ces classes sont donnés ci-dessous.

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

Les tests de grande baie peuvent être effectués de cette façon:

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Essayez-les sur Ideone

Je crois que j'ai un algorithme de O(k)temps et d' O(log(k))espace, étant donné que vous avez les fonctions floor(x)et log2(x)pour les entiers arbitrairement grands disponibles:

Vous avez un kentier long -bit (d'où l' log8(k)espace) où vous ajoutez le x^2, où x est le prochain numéro que vous trouvez dans le sac: s=1^2+2^2+...cela prend du O(N)temps (ce qui n'est pas un problème pour l'intervieweur). À la fin, vous obtenez j=floor(log2(s))le plus grand nombre que vous recherchez. Ensuite s=s-jet vous recommencez ce qui précède:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Maintenant, vous n'avez généralement pas de fonctions floor et log2 pour les 2756entiers -bit mais à la place pour les doubles. Donc? Simplement, pour chaque 2 octets (ou 1, ou 3 ou 4), vous pouvez utiliser ces fonctions pour obtenir les nombres souhaités, mais cela ajoute un O(N)facteur à la complexité temporelle

Cela peut sembler stupide, mais, dans le premier problème qui vous est présenté, vous devrez voir tous les nombres restants dans le sac pour les additionner afin de trouver le nombre manquant à l'aide de cette équation.

Donc, puisque vous pouvez voir tous les chiffres, recherchez simplement le numéro manquant. Il en va de même lorsque deux numéros sont manquants. Assez simple je pense. Inutile d'utiliser une équation lorsque vous voyez les nombres restants dans le sac.

Je pense que cela peut être généralisé comme ceci:

Notons S, M comme valeurs initiales pour la somme des séries arithmétiques et de la multiplication.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Je devrais penser à une formule pour calculer cela, mais ce n'est pas le point. Quoi qu'il en soit, s'il manque un numéro, vous avez déjà fourni la solution. Cependant, si deux nombres manquent alors, notons la nouvelle somme et le multiple total par S1 et M1, qui seront les suivants:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Puisque vous connaissez S1, M1, M et S, l'équation ci-dessus est résoluble pour trouver a et b, les nombres manquants.

Maintenant, pour les trois numéros manquants:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Maintenant, votre inconnu est 3 alors que vous n'avez que deux équations à résoudre.

Je ne sais pas si c'est efficace ou pas mais je voudrais suggérer cette solution.

1. Calculer le xor des 100 éléments
2. Calculer le xor des 98 éléments (après la suppression des 2 éléments)
3. Maintenant (résultat de 1) XOR (résultat de 2) vous donne le xor des deux nos manquants i..ea XOR b si a et b sont les éléments manquants
   4. Obtenez la somme des Nos manquants avec votre approche habituelle du formule de somme diff et disons que le diff est d.

Exécutez maintenant une boucle pour obtenir les paires possibles (p, q) qui se trouvent toutes les deux dans [1, 100] et additionnent à d.

Lorsqu'une paire est obtenue, vérifiez si (résultat de 3) XOR p = q et si oui, nous avons terminé.

Veuillez me corriger si je me trompe et commenter également la complexité du temps si cela est correct

On peut faire le Q1 et le Q2 en O (log n) la plupart du temps.

Supposons que notre se memory chipcompose d'un tableau de nnombre de test tubes. Et un certain nombre xdans le tube à essai est représenté par x milliliterdu liquide chimique.

Supposons que notre processeur soit un laser light. Lorsque nous allumons le laser, il traverse tous les tubes perpendiculairement à sa longueur. Chaque fois qu'il traverse le liquide chimique, la luminosité est réduite de 1. Et passer la lumière à une certaine marque de millilitre est une opération de O(1).

Maintenant, si nous allumons notre laser au milieu du tube à essai et obtenons la sortie de luminosité

• est égal à une valeur précalculée (calculée lorsqu'il n'y avait aucun chiffre manquant), alors les chiffres manquants sont supérieurs à n/2.
• Si notre sortie est plus petite, alors il y a au moins un nombre manquant qui est plus petit que n/2. On peut également vérifier si la luminosité est réduite de 1ou 2. s'il est réduit de 1alors un nombre manquant est plus petit que n/2et l'autre est plus grand que n/2. Si elle est réduite de, les 2deux nombres sont inférieurs à n/2.

Nous pouvons répéter le processus ci-dessus encore et encore en réduisant notre domaine de problème. À chaque étape, nous réduisons de moitié le domaine. Et enfin, nous pouvons arriver à notre résultat.

Des algorithmes parallèles qui méritent d'être mentionnés (car ils sont intéressants),

• le tri par un algorithme parallèle, par exemple, la fusion parallèle peut être effectué à O(log^3 n)temps. Et puis le nombre manquant peut être trouvé par recherche binaire dans le O(log n)temps.
• Théoriquement, si nous avons des nprocesseurs, chaque processus peut vérifier l'une des entrées et définir un indicateur qui identifie le nombre (commodément dans un tableau). Et à l'étape suivante, chaque processus peut vérifier chaque indicateur et finalement sortir le nombre qui n'est pas signalé. L'ensemble du processus prendra du O(1)temps. Il a O(n)besoin d'espace / mémoire supplémentaire .

Notez que les deux algorithmes parallèles fournis ci-dessus peuvent avoir besoin d'espace supplémentaire comme mentionné dans le commentaire .