Fizz Buzz

Easy Arrays & Hashing Simulation Original on LeetCode

Fizz Buzz is a easy arrays & hashing problem solved with the simulation pattern. The best approach, optimal (counters, no modulo), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (modulo checks) up.

Problem

Given a positive integer n, return a list of n strings where the entry for each number i from 1 to n (the list is 1-indexed by value) is:

  • "FizzBuzz" if i is divisible by both 3 and 5,
  • "Fizz" if i is divisible by 3 only,
  • "Buzz" if i is divisible by 5 only,
  • otherwise i written as a decimal string.

Examples

Example 1

Input
n = 5
Output
["1", "2", "Fizz", "4", "Buzz"]
Why
3 becomes "Fizz", 5 becomes "Buzz", the rest are written as numbers.

Example 2

Input
n = 16
Output
["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz", "16"]
Why
15 is divisible by both 3 and 5, so it becomes "FizzBuzz".

Constraints

  • 1 <= n <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (modulo checks)O(n)O(1)
Optimal (counters, no modulo)O(n)O(1)

1Brute force (modulo checks)

TimeO(n)A constant number of checks per value.
SpaceO(1)Nothing beyond the output list.

For every i from 1 to n, test divisibility by 15 first, then by 3, then by 5, and fall back to the number itself.

  1. For i = 1 … n:
  2. If i % 15 == 0 add "FizzBuzz"; else if i % 3 == 0 add "Fizz"; else if i % 5 == 0 add "Buzz"; else add the number as text.
class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> out = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) out.add("FizzBuzz");
            else if (i % 3 == 0) out.add("Fizz");
            else if (i % 5 == 0) out.add("Buzz");
            else out.add(String.valueOf(i));
        }
        return out;
    }
}

2Optimal (counters, no modulo)

TimeO(n)Two decrements and two comparisons per value.
SpaceO(1)Two counters besides the output.

Keep two countdowns, one that hits zero every 3 steps and one every 5 steps. Build the label by appending "Fizz" and/or "Buzz" when a countdown fires; if neither fired, use the number. This avoids division and extends easily to more rules.

  1. three = 3, five = 5.
  2. For i = 1 … n: decrement both; label = "".
  3. If three == 0: label += "Fizz", three = 3. If five == 0: label += "Buzz", five = 5.
  4. Add label, or the number if label is empty.
class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> out = new ArrayList<>();
        int three = 3, five = 5;
        for (int i = 1; i <= n; i++) {
            three--;
            five--;
            StringBuilder label = new StringBuilder();
            if (three == 0) { label.append("Fizz"); three = 3; }
            if (five == 0) { label.append("Buzz"); five = 5; }
            out.add(label.length() == 0 ? String.valueOf(i) : label.toString());
        }
        return out;
    }
}

Edge cases to test

  • n = 1: a single "1"
  • Multiples of 15 must become "FizzBuzz", not just "Fizz"

Hints

Hint 1

Which check has to come first so that 15 is not labelled only "Fizz"?

Hint 2

Can you avoid the % operator by keeping two counters that reset at 3 and at 5?

FAQ

What is the best time complexity for Fizz Buzz?

Optimal (counters, no modulo) runs in O(n) time and O(1) extra space. Two decrements and two comparisons per value.

Which pattern does Fizz Buzz use?

It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).

Is there a brute force solution for Fizz Buzz?

Yes. Brute force (modulo checks) takes O(n) time and O(1) space. For every i from 1 to n, test divisibility by 15 first, then by 3, then by 5, and fall back to the number itself.

Which edge cases should I test for Fizz Buzz?

n = 1: a single "1"; Multiples of 15 must become "FizzBuzz", not just "Fizz".