# 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`:

| Condition | Output |
|---|---|
| `i` is divisible by both `3` and `5` | `"FizzBuzz"` |
| `i` is divisible by `3` | `"Fizz"` |
| `i` is divisible by `5` | `"Buzz"` |
| None of the above | `i` as a string |

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

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | A list of strings from `1` to `n` |
| Divisible by `3` | Use `"Fizz"` |
| Divisible by `5` | Use `"Buzz"` |
| Divisible by both | Use `"FizzBuzz"` |
| Otherwise | Use the number as a string |

Example function shape:

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

## Examples

Example 1:

```python
n = 3
```

The output is:

```python
["1", "2", "Fizz"]
```

Explanation:

| Number | Output |
|---:|---|
| `1` | `"1"` |
| `2` | `"2"` |
| `3` | `"Fizz"` |

Example 2:

```python
n = 5
```

The output is:

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

Example 3:

```python
n = 15
```

The output is:

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

For `15`, both rules apply:

```python
15 % 3 == 0
15 % 5 == 0
```

So the output is:

```python
"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:

```python
"FizzBuzz"
```

We can handle this in two clean ways.

One way is to check divisibility by `15` first:

```python
if i % 15 == 0:
    ...
```

Another way is to build the string in pieces:

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

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

If both conditions are true, the result naturally becomes:

```python
"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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We process every number from `1` to `n` once |
| Space | `O(1)` extra | Apart from the required output list |

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

## Implementation

```python
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:

```python
answer = []
```

Then we loop from `1` to `n`:

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

For each number, we build the output string:

```python
text = ""
```

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

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

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

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

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

```python
"FizzBuzz"
```

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

```python
if not text:
    text = str(i)
```

Then we append the string for this number:

```python
answer.append(text)
```

Finally:

```python
return answer
```

## Testing

```python
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

| Test | Why |
|---|---|
| `n = 1` | Minimum input |
| `n = 3` | First `"Fizz"` |
| `n = 5` | First `"Buzz"` |
| `n = 15` | First `"FizzBuzz"` |
| `n = 30` | Checks repeated multiples of both `3` and `5` |