FizzBuzz

Q: What is the time complexity of FizzBuzz?

Answering for one number is O(1) : a fixed number of remainder checks and the conversion of a number with at most 10 digits. Printing the sequence from 1 to n is O(n) .

BeginnerMath and simulation

+10

In the counting game FizzBuzz, players count up from 1 and replace some numbers with words. Given a turn number n, return what a player says on that turn: "FizzBuzz" if n is divisible by both 3 and 5, "Fizz" if it is divisible by 3 only, "Buzz" if it is divisible by 5 only, and otherwise n itself written as a string, such as "7".

Function

fizzBuzz(n: integer) → string

ninteger: the turn number, a positive integer
Returnsstring: the word or number said on turn n, as a string

Constraints

1 ≤ n ≤ 10⁹
The answer is always a string, even when it is the number itself.

Examples

Input: n = 15
Output: "FizzBuzz"
Explanation: 15 divided by 3 is 5 and 15 divided by 5 is 3, both with no remainder, so turn 15 is "FizzBuzz".

Input: n = 7
Output: "7"
Explanation: 7 leaves a remainder of 1 when divided by 3 and 2 when divided by 5, so no word applies and you return the number as text, "7".

Follow-up

A new rule makes multiples of 7 "Bazz", words joined in order, so 105 is "FizzBuzzBazz". How do you add it without a case for every combination?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Each rule is one remainder check. The trap is the order: 15 is divisible by 3, so a function that tests 3 first and returns at once answers "Fizz" for 15. Either test the combined case first, or build the answer from both checks.

Build the word from both checks

Intuition

Start with an empty word. If 3 divides n, add "Fizz"; if 5 divides n, add "Buzz". Both checks always run, so a multiple of 15 collects both parts in order and becomes "FizzBuzz" with no special case. If the word is still empty, neither rule applied, and you return the number as a string.

Algorithm

Set word to an empty string.
If n % 3 == 0, append "Fizz".
If n % 5 == 0, append "Buzz".
If word is empty, return n converted to a string.
Otherwise return word.

def fizzBuzz(n):
    word = ""
    if n % 3 == 0:
        word += "Fizz"
    if n % 5 == 0:
        word += "Buzz"
    # An empty word means neither 3 nor 5 divides n.
    if word == "":
        return str(n)
    return word

Check 15, then 3, then 5

Intuition

A number divisible by both 3 and 5 is exactly a number divisible by 15, because 3 and 5 share no factor. So the combined rule is one check, n % 15 == 0, and it goes first. Once it fails, a match on 3 means 3 only and a match on 5 means 5 only. Each check returns at once, and if none matches you return the number as a string.

Algorithm

If n % 15 == 0, return "FizzBuzz".
If n % 3 == 0, return "Fizz".
If n % 5 == 0, return "Buzz".
Otherwise return n converted to a string, with every digit written out.

def fizzBuzz(n):
    if n % 15 == 0:
        return "FizzBuzz"
    if n % 3 == 0:
        return "Fizz"
    if n % 5 == 0:
        return "Buzz"
    return str(n)

Pitfalls and edge cases

Testing 3 or 5 before 15 and returning at once: 15, 30 and 45 come out as "Fizz".
Returning the number instead of a string. Turn 7 is "7".
Converting large numbers to scientific notation. In R a plain conversion prints 10^9 as 1e+09; use format(n, scientific = FALSE).
Printing the answer instead of returning it.

Frequently asked questions3

Why is FizzBuzz asked in coding interviews?

It checks that you can turn a short set of rules into working code: a remainder test, conditions in the right order, and the right return type. It takes a few minutes for someone who codes regularly, so it works as a quick screen before harder questions.

Can you solve FizzBuzz without the modulo operator?

Yes. Divide with integer division, multiply the quotient back and compare it with n: they are equal only when nothing is left over. When you print the whole sequence, you can also keep two counters that reset at 3 and at 5.

What is the time complexity of FizzBuzz?

Answering for one number is O(1): a fixed number of remainder checks and the conversion of a number with at most 10 digits. Printing the sequence from 1 to n is O(n).