FizzBuzz

Q: Quelle est la complexité temporelle de FizzBuzz ?

Répondre pour un nombre est en O(1) : un nombre fixe de vérifications du reste et la conversion d’un nombre comportant au plus 10 chiffres. Afficher la séquence de 1 à n est en O(n) .

DébutantMaths et simulation

+10

Dans le jeu de comptage FizzBuzz, les joueurs comptent à partir de 1 et remplacent certains nombres par des mots. Étant donné un numéro de tour n, renvoie ce qu'un joueur dit à ce tour : "FizzBuzz" si n est divisible à la fois par 3 et par 5, "Fizz" s'il est divisible uniquement par 3, "Buzz" s'il est divisible uniquement par 5, et sinon n lui-même écrit sous forme de chaîne, par exemple "7".

Fonction

fizzBuzz(n: integer) → string

ninteger: le numéro du tour, un entier positif
Renvoiestring: le mot ou le nombre prononcé au tour n, sous forme de chaîne

Contraintes

1 ≤ n ≤ 10⁹
La réponse est toujours une chaîne, même lorsqu’il s’agit du nombre lui-même.

Exemples

Entrée: n = 15
Sortie: "FizzBuzz"
Explication: 15 divisé par 3 donne 5 et 15 divisé par 5 donne 3, sans reste dans les deux cas, donc le tour 15 est "FizzBuzz".

Entrée: n = 7
Sortie: "7"
Explication: 7 a un reste de 1 lorsqu’il est divisé par 3 et de 2 lorsqu’il est divisé par 5, donc aucun mot ne s’applique et tu renvoies le nombre sous forme de texte, "7".

Pour aller plus loin

Une nouvelle règle transforme les multiples de 7 en "Bazz", les mots étant concaténés dans l’ordre, donc 105 donne "FizzBuzzBazz". Comment l’ajouter sans prévoir un cas pour chaque combinaison ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque règle est un test de reste. Le piège, c’est l’ordre : 15 est divisible par 3, donc une fonction qui teste 3 en premier et renvoie immédiatement répond "Fizz" pour 15. Teste d’abord le cas combiné, ou construis la réponse à partir des deux tests.

Formez le mot à partir des deux vérifications

Intuition

Commence par un mot vide. Si 3 divise n, ajoute "Fizz" ; si 5 divise n, ajoute "Buzz". Les deux vérifications sont toujours effectuées, donc un multiple de 15 rassemble les deux parties dans l’ordre et devient "FizzBuzz" sans cas particulier. Si le mot est toujours vide, aucune des deux règles ne s’est appliquée et tu renvoies le nombre sous forme de chaîne.

Algorithme

Définis word comme une chaîne vide.
Si n % 3 == 0, ajoute "Fizz".
Si n % 5 == 0, ajoute "Buzz".
Si word est vide, renvoie n converti en chaîne.
Sinon, renvoie word.

def fizzBuzz(n):
    word = ""
    if n % 3 == 0:
        word += "Fizz"
    if n % 5 == 0:
        word += "Buzz"
    # An empty word means neither 3 nor 5 divides n.
    if word == "":
        return str(n)
    return word

Vérifiez 15, puis 3, puis 5

Intuition

Un nombre divisible à la fois par 3 et par 5 est exactement un nombre divisible par 15, car 3 et 5 n’ont aucun facteur commun. La règle combinée consiste donc en une seule vérification, n % 15 == 0, et elle vient en premier. Si elle échoue, une correspondance avec 3 signifie 3 seulement et une correspondance avec 5 signifie 5 seulement. Chaque vérification renvoie immédiatement, et si aucune ne correspond, vous renvoyez le nombre sous forme de chaîne.

Algorithme

Si n % 15 == 0, renvoie "FizzBuzz".
Si n % 3 == 0, renvoie "Fizz".
Si n % 5 == 0, renvoie "Buzz".
Sinon, renvoie n converti en chaîne de caractères, avec chaque chiffre écrit en toutes lettres.

def fizzBuzz(n):
    if n % 15 == 0:
        return "FizzBuzz"
    if n % 3 == 0:
        return "Fizz"
    if n % 5 == 0:
        return "Buzz"
    return str(n)

Pièges et cas limites

Tester 3 ou 5 avant 15 et retourner immédiatement : 15, 30 et 45 donnent "Fizz".
Retourner le nombre au lieu d’une chaîne. Au tour 7, le résultat est "7".
Convertir les grands nombres en notation scientifique. Dans R, une conversion simple affiche 10^9 sous la forme 1e+09 ; utilisez format(n, scientific = FALSE).
Afficher la réponse au lieu de la retourner.

Questions fréquentes3

Pourquoi pose-t-on la question de FizzBuzz lors des entretiens de programmation ?

Il vérifie que tu sais transformer un court ensemble de règles en code fonctionnel : un test de reste, des conditions dans le bon ordre et le bon type de retour. Cela prend quelques minutes à une personne qui code régulièrement ; c’est donc un bon test rapide avant des questions plus difficiles.

Peux-tu résoudre FizzBuzz sans l’opérateur modulo ?

Oui. Divise avec une division entière, remultiplie le quotient et compare-le à n : ils sont égaux uniquement lorsqu’il ne reste rien. Lorsque tu affiches toute la séquence, tu peux aussi conserver deux compteurs qui se réinitialisent à 3 et à 5.

Quelle est la complexité temporelle de FizzBuzz ?

Répondre pour un nombre est en O(1) : un nombre fixe de vérifications du reste et la conversion d’un nombre comportant au plus 10 chiffres. Afficher la séquence de 1 à n est en O(n).

def fizzBuzz(n):
    # Écrivez le code ici

Test #1

Test #2

Argument

n = 15

Résultat attendu

"FizzBuzz"