Le moyen le plus rapide de trouver le nombre manquant dans un tableau de nombres

Question

J'ai un tableau de nombres de 1 à 100 (les deux inclus). La taille du tableau est de 100. Les nombres sont ajoutés au tableau de manière aléatoire, mais il existe un emplacement vide dans le tableau. Quel est le moyen le plus rapide de trouver cet emplacement ainsi que le nombre qui doit être placé dans cet emplacement ? Une solution Java est préférable.

Answer 1

Vous pouvez le faire en O(n). Faites un itération dans le tableau et calculez la somme de tous les nombres. Maintenant, la somme des nombres naturels de 1 à N, peut être exprimée comme suit Nx(N+1)/2 . Dans votre cas, N=100.

Soustraire la somme du tableau de Nx(N+1)/2 où N=100.

C'est le nombre manquant. L'emplacement vide peut être détecté pendant l'itération dans laquelle la somme est calculée.

// will be the sum of the numbers in the array.
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++)
{
    if (arr[i] == 0)
    {
         idx = i; 
    }
    else 
    {
         sum += arr[i];
    }
}

// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;

System.out.println("missing number is: " + (total - sum) + " at index " + idx);

Answer 2

Nous pouvons utiliser l'opération XOR qui est plus sûre que la sommation car, dans les langages de programmation, si l'entrée donnée est grande, elle peut déborder et donner une mauvaise réponse.

Avant de passer à la solution, sachez que A xor A = 0 . Donc, si on fait le XOR de deux nombres identiques, la valeur est 0.

Maintenant, en faisant le XOR [1..n] avec les éléments présents dans le tableau, on annule les nombres identiques. Ainsi, à la fin, nous obtiendrons le nombre manquant.

// Assuming that the array contains 99 distinct integers between 1..99
// and empty slot value is zero
int XOR = 0;
for(int i=0; i<100; i++) {
    if (ARRAY[i] != 0) // remove this condition keeping the body if no zero slot
        XOR ^= ARRAY[i];
    XOR ^= (i + 1);
}
return XOR;
//return XOR ^ ARRAY.length + 1; if your array doesn't have empty zero slot.

Answer 3

Supposons que le tableau donné soit A avec une longueur N. Supposons que dans le tableau donné, l'unique emplacement vide soit rempli de 0.

Nous pouvons trouver la solution de ce problème en utilisant de nombreuses méthodes, y compris l'algorithme utilisé dans Counting sort . Mais, en termes d'utilisation efficace du temps et de l'espace, nous avons deux algorithmes. L'un utilise principalement la sommation, la soustraction et la multiplication. L'autre utilise la méthode XOR. Mathématiquement, les deux méthodes fonctionnent bien. Mais d'un point de vue programmatique, nous devons évaluer tous les algorithmes à l'aide de mesures principales telles que

• Limites (par exemple, les valeurs d'entrée sont importantes) A[1...N] ) et/ou le nombre de valeurs d'entrée est important( N ))
• Nombre de contrôles d'état concernés
• Nombre et type d'opérations mathématiques impliquées

etc. Ceci est dû aux limitations de temps et/ou de matériel (limitation des ressources matérielles) et/ou de logiciel (limitation du système d'exploitation, limitation du langage de programmation, etc. Dressons une liste et évaluons les avantages et les inconvénients de chacun d'entre eux.

Algorithme 1 :

Dans l'algorithme 1, nous avons 3 implémentations.

1. Calculez la somme totale de tous les nombres (y compris le nombre manquant inconnu) en utilisant la formule mathématique( 1+2+3+...+N=(N(N+1))/2 ). Ici, N=100 . Calculez la somme totale de tous les nombres donnés. En soustrayant le deuxième résultat du premier, on obtient le nombre manquant.

   Missing Number = (N(N+1))/2) - (A[1]+A[2]+...+A[100])

2. Calculez la somme totale de tous les nombres (y compris le nombre manquant inconnu) en utilisant la formule mathématique( 1+2+3+...+N=(N(N+1))/2 ). Ici, N=100 . De ce résultat, soustrayez chaque nombre donné donne le nombre manquant.

   Missing Number = (N(N+1))/2)-A[1]-A[2]-...-A[100]

   ( Note: Même si la formule de la deuxième implémentation est dérivée de la première, d'un point de vue mathématique, les deux sont identiques. Mais du point de vue de la programmation, les deux sont différentes car la première formule est plus sujette au débordement de bits que la seconde (si les nombres donnés sont assez grands). Même si l'addition est plus rapide que la soustraction, la deuxième implémentation réduit le risque de débordement de bits causé par l'addition de grandes valeurs (il n'est pas complètement éliminé, car il y a toujours une très petite chance puisque ( N+1 ) est présent dans la formule). Mais les deux sont également sujets à un débordement de bits par multiplication. La limitation est que les deux implémentations donnent un résultat correct seulement si N(N+1)<=MAXIMUM_NUMBER_VALUE . Pour la première implémentation, la limitation supplémentaire est qu'elle donne un résultat correct seulement si Sum of all given numbers<=MAXIMUM_NUMBER_VALUE .)

3. Calculez la somme totale de tous les nombres (y compris le nombre manquant inconnu) et soustrayez chaque nombre donné dans la même boucle en parallèle. Cela élimine le risque de débordement de bits par la multiplication mais risque de débordement de bits par l'addition et la soustraction.

   //ALGORITHM missingNumber = 0; foreach(index from 1 to N) { missingNumber = missingNumber + index; //Since, the empty slot is filled with 0, //this extra condition which is executed for N times is not required. //But for the sake of understanding of algorithm purpose lets put it. if (inputArray[index] != 0) missingNumber = missingNumber - inputArray[index]; }

Dans un langage de programmation (comme C, C++, Java, etc.), si le nombre de bits représentant un type de données entières est limité, toutes les implémentations ci-dessus sont sujettes à un débordement de bits en raison de la sommation, de la soustraction et de la multiplication, ce qui donne un résultat erroné en cas de grandes valeurs d'entrée. A[1...N] ) et/ou un grand nombre de valeurs d'entrée ( N ).

Algorithme 2 :

Nous pouvons utiliser la propriété XOR pour résoudre ce problème sans nous soucier du problème de débordement de bits. De plus, XOR est à la fois plus sûr et plus rapide que la sommation. Nous connaissons la propriété du XOR selon laquelle le XOR de deux mêmes nombres est égal à 0( A XOR A = 0 ). Si nous calculons le XOR de tous les nombres de 1 à N (y compris le nombre manquant inconnu) et qu'avec ce résultat, nous XORons tous les nombres donnés, les nombres communs sont annulés (puisque A XOR A=0 ) et à la fin nous obtenons le numéro manquant. Si nous n'avons pas de problème de débordement de bits, nous pouvons utiliser les algorithmes basés sur la sommation et le XOR pour obtenir la solution. Mais l'algorithme qui utilise XOR est à la fois plus sûr et plus rapide que l'algorithme qui utilise la sommation, la soustraction et la multiplication. Et nous pouvons éviter les soucis supplémentaires causés par la sommation, la soustraction et la multiplication.

Dans toutes les implémentations de l'algorithme 1, nous pouvons utiliser XOR au lieu de l'addition et de la soustraction.

Supposons, XOR(1...N) = XOR of all numbers from 1 to N

Mise en œuvre 1 => Missing Number = XOR(1...N) XOR (A[1] XOR A[2] XOR...XOR A[100])

Mise en œuvre 2 => Missing Number = XOR(1...N) XOR A[1] XOR A[2] XOR...XOR A[100]

Mise en œuvre 3 =>

//ALGORITHM
missingNumber = 0;
foreach(index from 1 to N)
{
    missingNumber = missingNumber XOR index;
    //Since, the empty slot is filled with 0,
    //this extra condition which is executed for N times is not required.
    //But for the sake of understanding of algorithm purpose lets put it.
    if (inputArray[index] != 0)
        missingNumber = missingNumber XOR inputArray[index];
}

Les trois implémentations de l'algorithme 2 fonctionneront bien (d'un point de vue programmatique également). Une optimisation est, comme pour

1+2+....+N = (N(N+1))/2

Nous avons,

1 XOR 2 XOR .... XOR N = {N if REMAINDER(N/4)=0, 1 if REMAINDER(N/4)=1, N+1 if REMAINDER(N/4)=2, 0 if REMAINDER(N/4)=3}

Nous pouvons le prouver par induction mathématique. Ainsi, au lieu de calculer la valeur de XOR(1...N) en XORant tous les nombres de 1 à N, nous pouvons utiliser cette formule pour réduire le nombre d'opérations XOR.

De même, le calcul de XOR(1...N) à l'aide de la formule ci-dessus a deux implémentations. En termes d'implémentation, le calcul de

// Thanks to https://a3nm.net/blog/xor.html for this implementation
xor = (n>>1)&1 ^ (((n&1)>0)?1:n)

est plus rapide que de calculer

xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;

Ainsi, le code Java optimisé est,

long n = 100;
long a[] = new long[n];

//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0

//Slower way of implementing the formula
// long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
//Faster way of implementing the formula
// long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);
long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

for (long i = 0; i < n; i++)
{
    xor = xor ^ a[i];
}
//Missing number
System.out.println(xor);

Answer 4

Il s'agit d'une question d'entretien avec Amazon, à laquelle on a répondu ici : Nous avons des nombres de 1 à 52 qui sont placés dans un tableau de 51 nombres, quelle est la meilleure façon de trouver le nombre manquant ?

Il a été répondu, comme ci-dessous :

1) Calculate the sum of all numbers stored in the array of size 51. 
2) Subtract the sum from (52 * 53)/2 ---- Formula : n * (n + 1) / 2.

Il a également été publié sur ce blog : Emploi dans le secteur des logiciels - Question d'entretien

Answer 5

Voici un programme simple pour trouver les nombres manquants dans un tableau de nombres entiers.

ArrayList<Integer> arr = new ArrayList<Integer>();
int a[] = { 1,3,4,5,6,7,10 };
int j = a[0];
for (int i=0;i<a.length;i++)
{
    if (j==a[i])
    {
        j++;
        continue;
    }
    else
    {
        arr.add(j);
        i--;
    j++;
    }
}
System.out.println("missing numbers are ");
for(int r : arr)
{
    System.out.println(" " + r);
}