FizzBuzz

Q: ¿Cuál es la complejidad temporal de FizzBuzz?

Responder para un número es O(1) : una cantidad fija de comprobaciones del resto y la conversión de un número de como máximo 10 dígitos. Imprimir la secuencia del 1 a n es O(n) .

PrincipianteMatemáticas y simulación

+10

En el juego de contar FizzBuzz, los jugadores cuentan desde 1 y reemplazan algunos números por palabras. Dado un número de turno n, devuelve lo que dice un jugador en ese turno: "FizzBuzz" si n es divisible entre 3 y 5, "Fizz" si solo es divisible entre 3, "Buzz" si solo es divisible entre 5 y, en caso contrario, el propio n escrito como una cadena, como "7".

Función

fizzBuzz(n: integer) → string

ninteger: el número de turno, un entero positivo
Devuelvestring: la palabra o el número que se dice en el turno n, como cadena

Restricciones

1 ≤ n ≤ 10⁹
La respuesta siempre es una cadena, incluso cuando es el propio número.

Ejemplos

Entrada: n = 15
Salida: "FizzBuzz"
Explicación: 15 dividido entre 3 es 5 y 15 dividido entre 5 es 3, ambos sin resto, así que el turno 15 es "FizzBuzz".

Entrada: n = 7
Salida: "7"
Explicación: 7 deja un resto de 1 al dividirse entre 3 y de 2 al dividirse entre 5, así que no se aplica ninguna palabra y devuelves el número como texto, "7".

Para ir más allá

Una nueva regla convierte los múltiplos de 7 en "Bazz", con las palabras concatenadas en orden, así que 105 es "FizzBuzzBazz". ¿Cómo la agregas sin crear un caso para cada combinación?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada regla es una comprobación del resto. La trampa está en el orden: 15 es divisible por 3, así que una función que comprueba primero 3 y devuelve el resultado de inmediato responde "Fizz" para 15. Comprueba primero el caso combinado o construye la respuesta a partir de ambas comprobaciones.

Construye la palabra a partir de ambas comprobaciones

Intuición

Empieza con una palabra vacía. Si 3 divide a n, añade "Fizz"; si 5 divide a n, añade "Buzz". Ambas comprobaciones se ejecutan siempre, así que un múltiplo de 15 reúne ambas partes en orden y se convierte en "FizzBuzz" sin ningún caso especial. Si la palabra sigue vacía, no se aplicó ninguna de las reglas y devuelves el número como una cadena.

Algoritmo

Establece word como una cadena vacía.
Si n % 3 == 0, añade "Fizz".
Si n % 5 == 0, añade "Buzz".
Si word está vacío, devuelve n convertido en una cadena.
De lo contrario, devuelve 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

Comprueba 15, después 3, después 5

Intuición

Un número divisible tanto por 3 como por 5 es exactamente un número divisible por 15, porque 3 y 5 no comparten ningún factor. Así que la regla combinada es una sola comprobación, n % 15 == 0, y va primero. Si no se cumple, una coincidencia con 3 significa solo 3 y una coincidencia con 5 significa solo 5. Cada comprobación devuelve el resultado de inmediato y, si ninguna coincide, devuelves el número como una cadena.

Algoritmo

Si n % 15 == 0, devuelve "FizzBuzz".
Si n % 3 == 0, devuelve "Fizz".
Si n % 5 == 0, devuelve "Buzz".
En caso contrario, devuelve n convertido en una cadena, con cada dígito escrito.

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

Errores comunes y casos límite

Probar 3 o 5 antes que 15 y devolver el resultado de inmediato: 15, 30 y 45 dan como resultado "Fizz".
Devolver el número en lugar de una cadena. El turno 7 es "7".
Convertir números grandes a notación científica. En R, una conversión simple muestra 10^9 como 1e+09; usa format(n, scientific = FALSE).
Imprimir la respuesta en lugar de devolverla.

Preguntas frecuentes3

¿Por qué se pregunta por FizzBuzz en las entrevistas de programación?

Comprueba que puedes convertir un conjunto breve de reglas en código funcional: una prueba del resto, condiciones en el orden correcto y el tipo de retorno adecuado. A alguien que programa con regularidad le lleva unos minutos, así que sirve como una prueba rápida antes de preguntas más difíciles.

¿Puedes resolver FizzBuzz sin el operador módulo?

Sí. Divide mediante división entera, multiplica de nuevo el cociente y compáralo con n: solo son iguales cuando no queda ningún resto. Cuando imprimas toda la secuencia, también puedes llevar dos contadores que se reinicien en 3 y en 5.

¿Cuál es la complejidad temporal de FizzBuzz?

Responder para un número es O(1): una cantidad fija de comprobaciones del resto y la conversión de un número de como máximo 10 dígitos. Imprimir la secuencia del 1 a n es O(n).

def fizzBuzz(n):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

n = 15

Salida Esperada

"FizzBuzz"