LeetCode 412: Fizz Buzz

Problem Restatement

We are given an integer n.

Return a string array answer of length n.

For every integer i from 1 to n:

The array is 1-indexed in the problem description, meaning answer[i] describes the value for number i. In Python, we still store it in a normal 0-indexed list. The source constraints include 1 <= n <= 10^4.

Input and Output

Example function shape:

def fizzBuzz(n: int) -> list[str]:
    ...

Examples

Example 1:

n = 3

The output is:

["1", "2", "Fizz"]

Explanation:

Example 2:

n = 5

The output is:

["1", "2", "Fizz", "4", "Buzz"]

Example 3:

n = 15

The output is:

[
    "1", "2", "Fizz", "4", "Buzz",
    "Fizz", "7", "8", "Fizz", "Buzz",
    "11", "Fizz", "13", "14", "FizzBuzz",
]

For 15, both rules apply:

15 % 3 == 0
15 % 5 == 0

So the output is:

"FizzBuzz"

First Thought: Direct Simulation

The problem gives a rule for each number.

So the simplest method is to simulate those rules from 1 through n.

For each number:

1. Check whether it is divisible by 3.
2. Check whether it is divisible by 5.
3. Return the correct string for that number.

This is already efficient because we must produce n output strings anyway.

Key Insight

The number divisible by both 3 and 5 should produce:

"FizzBuzz"

We can handle this in two clean ways.

One way is to check divisibility by 15 first:

if i % 15 == 0:
    ...

Another way is to build the string in pieces:

if i % 3 == 0:
    text += "Fizz"

if i % 5 == 0:
    text += "Buzz"

If both conditions are true, the result naturally becomes:

"FizzBuzz"

This avoids needing a separate special case for 15.

Algorithm

Create an empty list answer.

For every integer i from 1 to n:

1. Start with an empty string text.
2. If i is divisible by 3, append "Fizz" to text.
3. If i is divisible by 5, append "Buzz" to text.
4. If text is still empty, set it to str(i).
5. Append text to answer.

Return answer.

Correctness

For each integer i, the algorithm checks the divisibility rules from the problem.

If i is divisible by 3, the algorithm adds "Fizz".

If i is divisible by 5, the algorithm adds "Buzz".

If both conditions hold, both words are added, producing "FizzBuzz".

If neither condition holds, no word is added, so the algorithm uses str(i).

Thus, for every number from 1 to n, the algorithm appends exactly the required output string. Since it processes all numbers in increasing order, the returned list has the correct order and content.

Complexity

The output list itself has length n, so total returned storage is O(n).

Implementation

from typing import List

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        answer = []

        for i in range(1, n + 1):
            text = ""

            if i % 3 == 0:
                text += "Fizz"

            if i % 5 == 0:
                text += "Buzz"

            if not text:
                text = str(i)

            answer.append(text)

        return answer

Code Explanation

We store the result in:

answer = []

Then we loop from 1 to n:

for i in range(1, n + 1):

For each number, we build the output string:

text = ""

If the number is divisible by 3, we add "Fizz":

if i % 3 == 0:
    text += "Fizz"

If the number is divisible by 5, we add "Buzz":

if i % 5 == 0:
    text += "Buzz"

For a number like 15, both conditions run, so text becomes:

"FizzBuzz"

If no condition ran, text remains empty, so we use the number itself:

if not text:
    text = str(i)

Then we append the string for this number:

answer.append(text)

Finally:

return answer

Testing

def test_fizz_buzz():
    s = Solution()

    assert s.fizzBuzz(1) == ["1"]

    assert s.fizzBuzz(3) == [
        "1", "2", "Fizz",
    ]

    assert s.fizzBuzz(5) == [
        "1", "2", "Fizz", "4", "Buzz",
    ]

    assert s.fizzBuzz(15) == [
        "1", "2", "Fizz", "4", "Buzz",
        "Fizz", "7", "8", "Fizz", "Buzz",
        "11", "Fizz", "13", "14", "FizzBuzz",
    ]

    result = s.fizzBuzz(30)
    assert result[2] == "Fizz"
    assert result[4] == "Buzz"
    assert result[14] == "FizzBuzz"
    assert result[29] == "FizzBuzz"

    print("all tests passed")

Test Notes