Dans le problème du nombre manquant:

Trouver le nombre manquant dans un tableau entier donné de 1 à 100?

Voici le code en python pour ce problème:

N ne peut pas être prédéfini car il dépend du tableau affecté dans la fonction

def missingNumber(nums):
    n = len(nums)
    total = (n+1)*(n+2)/2
    missing = total - sum(nums)
    return missing

missingNumber([1, 2, 4, 5, 6])

Je ne comprends pas la logique de la façon de trouver

total = (n+1)*(n+2)/2
0
stillearning 27 janv. 2019 à 06:33

3 réponses

Meilleure réponse

On vous donne que, un numéro est manquant dans un tableau de nombres consécutifs,

Supposons que vous connaissez la somme des n premiers nombres. Soit la somme des n premiers nombres s. Maintenant qu'un nombre est manquant dans les n premiers nombres, nous pouvons obtenir le nombre manquant comme

s - sum of remaining numbers

Voyons maintenant comment calculer s,

Disons que j'ai des nombres "1, 2, 3, 4, 5, ...., 100"

Maintenant, je veux calculer la somme d'entre eux,

Une chose que je peux faire est soit de l’alimenter dans un programme informatique / une calculatrice, soit de prendre la somme un par un.

L'autre façon dont le jeune Gauss est apparu lorsque son professeur lui a posé cette question était:

let s1 = 1 + 2 + 3 + ... + 100

take the reverse of it,

let s2 = 100 + 99 + 98 + ... + 1

Now add s1 and s2

s1 + s2 = (100 + 1) + (99 + 2) + .... + (1 + 100)

but s1 = s2, so,

2s1 = 101 + 101 + ... + 101 // sequence has 100 terms

s1 = (101)*(100) / 2 // sum of first 100 numbers

Nous avons donc, somme des n premiers nombres comme (n)*(n+1)/2 d'une manière généralisée. Cela peut également être prouvé par induction mathématique.

Pour votre problème si n est la longueur du tableau avec un nombre manquant, alors n + 1 doit être la taille du tableau d'origine. donc s = (n+1)*(n+2)/2

2
HariUserX 27 janv. 2019 à 05:46

Si vous cherchez à trouver un seul numéro manquant, voici le code,

def missingNumber(nums):
    n = nums[-1]
    total = (n)*(n+1)/2
    missing = total - sum(nums)
    return missing

Si vous souhaitez trouver plusieurs numéros manquants, le code ci-dessous pourrait vous aider,

def missingNumbers(nums):
    missingNumbers = []
    count = 0
    for n in range(nums[-1]):
        if n + 1 != nums[count]:
            missingNumbers.append(n + 1)
        else:
            count = count + 1
    return missingNumbers

Les deux codes supposent que l'entrée commence toujours par un et augmente par pas de un.

1
Suresh 27 janv. 2019 à 05:37

Vous ne devriez pas avoir n comme argument. Cela soulèvera l'erreur. TypeError: missingNumber () manquant 1 argument positionnel requis: 'n'

Et n est défini plus loin dans la fonction.

Il y a aussi une erreur dans la fonction.

Par exemple, si num = [1,2,3,4,5,6], la sortie sera 7 mais votre tableau est censé se terminer à 6.

La réponse à votre question: -

(n + 1) * (n + 2) / 2 est la somme des premiers n + 1 nombres naturels

1
user8288709user8288709 27 janv. 2019 à 04:04