On nous donne une liste des entiers N-1 et ces entiers sont compris entre 1 et n. Il n'y a pas de doublons dans la liste. L'un des entiers est manquant dans la liste. Nous devons trouver le numéro manquant. C'est la question.
Mon approche consiste à prendre xor de tous les éléments de 1 ... n et à tous les éléments du tableau, puis de sortie XOR. Cela fonctionne bien, mais j'ai trouvé une solution de plus dans les geeks pour les geeks, mais je ne suis pas capable de comprendre quoi et pourquoi le fait le faire.
Approche : nous pouvons choisir un chiffre des numéros connus et soustrayez un chiffre des nombres donnés
3 Réponses :
Utilisez la formule SUM:
somme de i = 1 à n = n * (n + 1) / 2
https: //fr.wikipedia .org / wiki / 1_% 2b_2_% 2B_3_% 2B_4_% 2B_% E2% 8B% AF
Ajouter les chiffres de la liste. Soustrayez-le de la somme des chiffres et vous avez votre numéro manquant.
Cela causera trop de débordement et je ne demandais pas une nouvelle solution, mais je vous demandais d'expliquer l'approche donnée. S'il vous plaît répondre selon la question posée
for ( i = 2; i<= (n+1); i++)
{
total+=i;
total -= a[i-2]; // This will reduce the total so that overflow does not happen.
}
Donc, fondamentalement, nous faisons la sommation du premier nombre naturel et la soustraits de la somme de la matrice simultanée pour éviter le débordement. Corriger?
Oui. afin que le débordement ne se produise pas.
@backdoor: correct. Comme il n'y a qu'un numéro manquant, Total changements de 0 ou 1 à chaque étape, et il y en a à la plupart des étapes N-1.
à l'intérieur de la boucle pour la boucle:
As total= sum(1 to N) - sum(array elements)= missing number.
Est-ce moi, ou dans les derniers jours, Stackoverflow a été transformé en site de commentaire Geeksforgeeks?
Désolé ... c'était une bonne approche, donc je ne pouvais pas résister à ne pas le savoir.
@Paulmckenzie Je blâme les parents.