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.

Count the Fizz, Buzz and FizzBuzz entries for any n without building the list.

Use inclusion and exclusion. FizzBuzz is n // 15. Fizz is n // 3 - n // 15, because the multiples of 15 were counted among the multiples of 3 and belong to FizzBuzz. Buzz is n // 5 - n // 15. The plain numbers are what is left: n - n // 3 - n // 5 + n // 15, where the last term adds back the multiples of 15 that were subtracted twice. For n = 10⁴ that gives 666, 2,667, 1,334 and 5,333, the same counts the full list produces, in O(1) time.

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.

The trap itself, overlapping rules evaluated in order where the first match wins, is everywhere in production code, and the fix is always the same: put the most specific rule first, or make the rules independent so their order stops mattering.

• Exception handlers. In Python, an except Exception placed above an except ValueError catches every ValueError first, and the specific handler never runs, with no warning. Java refuses to compile the same mistake, reporting that the subclass exception has already been caught.
• Firewall and access rules. First-match rule lists behave like an elif chain: a broad “allow” placed above a narrow “deny” silently disables the deny.
• Request routing. Routers that try routes in registration order send /users/me to a /users/:id handler registered above it, with id = "me".
• IP routing. Routing tables avoid the problem by rule rather than by order: the longest matching prefix wins, so a /24 route always beats the /16 that contains it, wherever it sits in the table.

That last design is the build-the-word FizzBuzz in another form: specificity is decided by the data, not by where a line happens to be written, which is why it keeps working as rules are added. When you review a chain of overlapping conditions, ask of each branch whether any input that reaches it could also satisfy a branch above it.

Check yourself

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"]