Fizz Buzz

Start from brute force

The obvious first draft tests the rules in the order the problem states them: if i % 3 == 0 appends “Fizz”, elif i % 5 == 0 appends “Buzz”, elif i % 15 == 0 appends “FizzBuzz”, and otherwise the number. It runs in O(n) time with O(n) space for the list, and it is right for 14 of the first 15 numbers. It is wrong at 15 and at every multiple of 15 after it, because every multiple of 15 is also a multiple of 3: the first branch catches it, and an elif chain never looks further. Up to 10,000 this draft never prints “FizzBuzz” once. Speed was never the problem; the order of overlapping conditions is.

The approach

The insight is that the rules overlap, and an if/elif chain is decided by its first true branch, so the most specific rule has to come first. Divisible by both 3 and 5 is the same as divisible by 15, because 3 and 5 share no factor and 15 is their least common multiple, so one test, i % 15 == 0, covers the combined case. The invariant: after the iteration for i, out holds exactly i strings and out[i - 1] is the answer for i.

The reference loops for i in range(1, n + 1), so 1 and n are both included and there is no entry for 0. It checks i % 15 == 0 first and appends “FizzBuzz”, then i % 3 == 0 for “Fizz”, then i % 5 == 0 for “Buzz”, and otherwise appends str(i), because every element must be a string. An equally correct shape builds the word from two independent checks and falls back to the number when the word is empty; that version has no ordering trap at all.

Walk through an example

The second example, n = 15, traced with the three remainders the chain can test; its first five rows are the first example.

Complexity

Reference: O(n) time, a fixed number of modulo checks and one append per number, and O(n) space for the returned list; strictly, the digits written grow as O(n log n) characters. Nothing can beat O(n), because the output has n entries. Naive chain: the same O(n) time and space. Its problem is order, not cost.

Edge cases to test

• n = 1: ["1"]. The loop starts at 1; starting at 0 adds a “FizzBuzz” for 0, because 0 % 15 == 0, and drops the last number.
• n = 15: the last entry is “FizzBuzz”. A chain that tests 3 first returns “Fizz” there.
• n = 30: indices 14 and 29 are both “FizzBuzz”. Every multiple of 15 must reach the first branch, not just 15 itself.
• n = 2: ["1", "2"], strings rather than the integers [1, 2]. A list of ints fails the equality check.
• n = 10⁴, the upper bound: 10,000 strings, of which 666 are “FizzBuzz”, 2,667 “Fizz”, 1,334 “Buzz” and 5,333 plain numbers.
• n = 0, outside the stated range: range(1, 1) is empty, so the reference returns [] rather than raising.

Common mistakes

• Checking 3 and 5 before 15, so multiples of 15 print “Fizz” instead of “FizzBuzz”.
• Off-by-one on the range (starting at 0, or missing the last number).
• Appending the plain numbers as integers: fizzbuzz(2) must be ["1", "2"], and [1, 2] is not equal to it.
• Over-engineering a five-line problem: a rule table earns its place once there are several rules, but for two rules a plain loop that is obviously correct is the better answer.

Follow-ups an interviewer asks next

Add a rule: multiples of 7 print “Bazz”.

The if/elif chain stops scaling, because three rules have seven non-empty combinations, each needing its own branch in the right order. Build the word instead: keep an ordered list of (divisor, word) pairs, join the words whose divisor divides i, and fall back to str(i) when nothing matched. Then 21 gives “FizzBazz”, 35 “BuzzBazz” and 105 “FizzBuzzBazz” with no extra code.

Solve it without the modulo operator.

Keep two countdown counters, one starting at 3 and one at 5. Each iteration decrements both; when one reaches zero, add its word and reset it to 3 or 5. That replaces division with subtraction and produces exactly the same list, which you can confirm by comparing it with the modulo version for every n up to 10,000.

n is a billion. Do not build the list.

Yield each string from a generator, so the extra memory stays O(1) instead of O(n). You can also use the fact that the pattern repeats every 15 numbers: precompute the 15-entry cycle once and look up (i - 1) % 15, writing str(i) wherever the cycle has no word.

Where this shows up

FizzBuzz is the classic screening warm-up — it filters for basic control flow and, subtly, for handling the combined case in the right order. Trivial as it is, the divisibility-ordering trap is a real one that catches rushed candidates.

Reference solution

def fizzbuzz(n):
    out = []
    for i in range(1, n + 1):
        if i % 15 == 0:          # both 3 and 5 — check this FIRST
            out.append("FizzBuzz")
        elif i % 3 == 0:
            out.append("Fizz")
        elif i % 5 == 0:
            out.append("Buzz")
        else:
            out.append(str(i))   # plain number, as a string
    return out


print(fizzbuzz(5))    # -> ['1', '2', 'Fizz', '4', 'Buzz']

function fizzbuzz(n: number): string[] {
  const out: string[] = [];
  for (let i = 1; i <= n; i++) {
    if (i % 15 === 0) {           // both 3 and 5 — check this FIRST
      out.push("FizzBuzz");
    } else if (i % 3 === 0) {
      out.push("Fizz");
    } else if (i % 5 === 0) {
      out.push("Buzz");
    } else {
      out.push(String(i));        // plain number, as a string
    }
  }
  return out;
}

console.log(fizzbuzz(5));         // -> ["1","2","Fizz","4","Buzz"]