Fizz Buzz Problem

Difficulty: Easy, Asked-In: Google, Microsoft, Amazon.

Key takeaway: The FizzBuzz game is a popular problem that is more about learning basic programming concepts such as if-else, loops, string operations, mathematical operations, optimizations, etc.

Let’s understand the problem!

This game is played in a group, where players take turns to say the next number in a sequence, counting one at a time.

• If the number is divisible by 3, the player must say “Fizz” instead of the number itself.
• If the number is divisible by 5, the player must say “Buzz”.
• If the number is divisible by 3 and 5, the player must say “FizzBuzz”.

Given a number n, write a program that outputs the string representation of numbers from 1 to n. We need to return a string array as an output (1-indexed) where:

• output[i] = "FizzBuzz" if i is divisible by 3 and 5.
• output[i] = "Fizz" if i is divisible by 3.
• output[i] = "Buzz" if i is divisible by 5.
• output[i] = "i" if none of the above conditions are true.

Important note: Before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

Example

Input: n = 15

Output: ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz"]

Discussed solution approaches

• Using modulus operation
• Without using modulus operations
• Using string concatenation
• Using hash table

Using modulus operation

Solution idea

The most basic solution is to run a loop from 1 to n and use the modulus operation. In this loop, we employ a sequence of conditional statements to check whether each integer is divisible by 3 or 5 or both. When one of the conditional statements returns true, we store the appropriate string value at the ith index in the output[] string. Once the loop has been completed, we return the output[] string.

Solution steps

1. We define an empty output[] string of size n.
2. We run a loop from 1 to n and check divisibility by 3 or 5 or both.
3. For i is divisible by both 3 and 5, we add the string "FizzBuzz" at ith index of the output string. 
4. Else, if integer i is divisible by 3, we add "Fizz".
5. Else, if integer i is divisible by 5, we add "Buzz".
6. Else, we add the string value of integer i.

Implementation code C++

// Function to implement the FizzBuzz game
string* fizzBuzzGame(int n)
{
    // Initialize an array of strings to store the output
    string *output = new string[n];

    // Iterate over the range 1 to n
    for (int i = 1; i <= n; i =  i + 1)
    {
        // Check if the current number is divisible by 3 and 5
        if ((i % 3 == 0) && (i % 5 == 0))
            output[i-1] = "FizzBuzz";

        // Check if the current number is divisible by 3
        else if ((i % 3) == 0)
            output[i - 1] = "Fizz";

        // Check if the current number is divisible by 5
        else if ((i % 5) == 0)
            output[i-1] = "Buzz";

        // If the number is not divisible by 3 or 5, store the number itself
        else
            output[i-1] = to_string(i);
    }

    return output;
}

Implementation code Python

def fizzBuzzGame(n):
    output = []
    for i in range(1, n + 1):
        if (i % 3 == 0) and (i % 5 == 0):
            output.append("FizzBuzz")

        elif (i % 3) == 0:
            output.append("Fizz")

        elif (i % 5) == 0:
            output.append("Buzz")

        else:
            output.append(str(i))

    return output

Implementation code Java

public class FizzBuzz 
{
    public List<String> fizzBuzzGame(int n) 
    {
        List<String> output = new ArrayList<>();

        for (int i = 1; i <= n; i = i + 1) 
        {
            if (i % 3 == 0 && i % 5 == 0)
                output.add("FizzBuzz");

            else if (i % 3 == 0)
                output.add("Fizz");
            
            else if (i % 5 == 0)
                output.add("Buzz");
            
            else
                output.add(String.valueOf(i));
        }

        return output;
    }
}

Solution analysis

We are running a single loop and performing constant operations at each iteration. So the time complexity is O(n). We are using constant extra space, so the space complexity is O(1).

Note: The above code works perfectly, but there are some limitations:

1. The statements i % 3 == 0 and i % 5 == 0 are repeated twice, making the code inefficient.
2. At a low level, the modulo operation is a division operation that can be costly in terms of performance, especially for large integers.
3. It uses a lot of messy conditional statements, which are hard to maintain when the number of divisibility conditions increases in the problem.

Without using modulus operations

Now, the critical question is: How can we solve the Fizz Buzz problem without using the modulo operation? Let's think!

When we explore each number from the start, the word "Fizz" will appear after every cycle of 3. Similarly, the word "Buzz" will appear after every cycle of 5. So, what happens when both words need to be printed together? The answer is simple: "FizzBuzz" will appear after the cycle of 15 because 15 is the lowest number divisible by both 3 and 5. Think about it!

Using the above insight, let's track the appearance cycles of the words "Fizz" and "Buzz" using two variables: fizzCount and buzzCount. At the start, we initialize both variables to 0 and run a loop from i = 1 to n. At each iteration, we increment fizzCount and buzzCount by 1 and keep track of the cycles of 3 and 5.

• We reset fizzCount = 0 when fizzCount == 3. 
• We reset buzzCount = 0 when buzzCount == 5. 

Now, there are four scenarios:

1. fizzCount != 3 and buzzCount != 5: We store the string value of number i at the ith index of the output string.
2. fizzCount == 3 and buzzCount != 5: We store the word "Fizz" at the ith index of the output string and set fizzCount = 0.
3. fizzCount != 3 and buzzCount == 5: We store the word "Buzz" at the ith index of the output string and set buzzCount = 0.
4. fizzCount == 3 and buzzCount == 5: We store the word "FizzBuzz" at the ith index of the output string and set both buzzCount and fizzCount equal to 0.

Implementation code C++

string* fizzBuzzGame(int n)
{
    // Initialize an array of strings to store the output
    string *output = new string[n];
    // Initialize counters for Fizz and Buzz
    int fizzCount = 0;
    int buzzCount = 0;
    for (int i = 1; i <= n; i = i + 1)
    {
        fizzCount = fizzCount + 1;
        buzzCount = buzzCount + 1;
        // Check if the current number is divisible by 3 and 5
        if (fizzCount == 3 && buzzCount == 5)
        {
            output[i-1] = "FizzBuzz";
            fizzCount = 0;
            buzzCount = 0;
        }
        // Check if the current number is divisible by 3
        else if (fizzCount == 3)
        {
            output[i-1] = "Fizz";
            fizzCount = 0;
        }
        // Check if the current number is divisible by 5
        else if (buzzCount == 5)
        {
            output[i-1] = "Buzz";
            buzzCount = 0;
        }
        // If the number is not divisible by 3 or 5, store the number itself
        else
        {
            output[i-1] = to_string(i);
        }
    }

    return output;
}

Implementation code Python

def fizzBuzzGame(n):
    output = []
    fizzCount = 0
    buzzCount = 0
    for i in range(1, n + 1):
        fizzCount = fizzCount + 1
        buzzCount = buzzCount + 1
        if fizzCount == 3 and buzzCount == 5:
            output.append("FizzBuzz")
            fizzCount = 0
            buzzCount = 0
        elif fizzCount == 3:
            output.append("Fizz")
            fizzCount = 0
        elif buzzCount == 5:
            output.append("Buzz")
            buzzCount = 0
        else:
            output.append(str(i))

    return output

Implementation code Java

public class FizzBuzz 
{
    public List<String> fizzBuzzGame(int n) 
    {
        List<String> output = new ArrayList<>();
        int fizzCount = 0;
        int buzzCount = 0;

        for (int i = 1; i <= n; i =  i + 1) 
        {
            fizzCount = fizzCount + 1;
            buzzCount = buzzCount + 1;

            if (fizzCount == 3 && buzzCount == 5) 
            {
                output.add("FizzBuzz");
                fizzCount = 0;
                buzzCount = 0;
            }
            else if (fizzCount == 3) 
            {
                output.add("Fizz");
                fizzCount = 0;
            }
            else if (buzzCount == 5) 
            {
                output.add("Buzz");
                buzzCount = 0;
            }
            else
                output.add(Integer.toString(i));
        }

        return output;
    }
}

Solution analysis

We are running a single loop and doing constant operations at each iteration. So time complexity = O(n). We are using constant extra space, so space complexity = O(1).

Using string concatenation

Solution idea

In the above solution, we are still using a lot of conditional statements. Now critical question is: Can we reduce the number of conditional statements in the loop? Let's think! 

For example, if the problem gets modified from FizzBuzz to FizzBuzzJazz i.e. store "Fizz" if the integer is 3, store "Buzz" if the integer is 5, and store "Jazz" if the integer is 7. If we try to solve this with the previous approach, we need to check several divisibility conditions:

• Divisible by 3, divisible by 5, divisible by 7
• Divisible by 3 and 5, divisible by 3 and 7, divisible by 7 and 3
• Divisible by 3 and 5 and 7, Not divisible by 3 or 5 or 7.

If FizzBuzz mappings increase further, the number of conditional statements will grow exponentially in our code. So instead of checking for every possible combination of these conditional statements, we only check for divisibility by given numbers in the problem i.e. 3 and 5. If the number is divisible, we concatenate the corresponding string "Fizz" or "Buzz" to the output[] string.

So for FizzBuzz, we just check for two conditions. Similarly, for FizzBuzzJazz, we would have three conditions to check for divisibility.

Solution steps

Step 1: We define an empty output[] string of size n.

Step 2: Now we run a loop from i = 1 to n. At each iteration:

• We start by defining an empty string s. 
• If i is divisible by 3, we add “Fizz” at the end of the empty string s. 
• Similarly, if i is divisible by 5, we add “Buzz” at the end of the empty string s. 
• Now we check whether string s is empty or not. If yes, we store the string value of integer i in the empty string s. 
• Finally, we store the value of s at output[i].

Step 3: Once the loop is over, we return the output[] string as an output.

Implementation code C++

string* fizzBuzzGame(int n)
{
    // Initialize an array of strings to store the output
    string *output = new string[n];
    for (int i = 1; i <= n; i =  i + 1)
    {
        string s = "";
        // Check if the current number is divisible by 3
        if ((i % 3) == 0)
            s = s + "Fizz";
        // Check if the current number is divisible by 5
        if ((i % 5) == 0)
            s = s + "Buzz";
        // If the number is not divisible by 3 or 5, store the number itself
        if (s == "")
            s = s + to_string(i);

        output[i-1] = s;
    }

    return output;
}

Implementation code Python

def fizzBuzzGame(n):
    output = []
    for i in range(1, n+1):
        s = ""
        if (i % 3) == 0:
            s = s + "Fizz"
        if (i % 5) == 0:
            s = s + "Buzz"
        if s == "":
            s = s + str(i)

        output.append(s)

    return output

Implementation code Java

public class FizzBuzz
{
    public List<String> fizzBuzzGame(int n) 
    {
        List<String> output = new ArrayList<>();
        for (int i = 1; i <= n; i = i + 1) 
        {
            String s = "";
            if (i % 3 == 0)
                s = s + "Fizz";
            if (i % 5 == 0)
                s = s + "Buzz";
            if (s.isEmpty())
                s = s + Integer.toString(i);

            output.add(s);
        }

        return output;
    }
}

Solution analysis

We are running a single loop and doing constant operations at each iteration. So time complexity = O(n). We are using constant extra space, so space complexity = O(1).

Using hash table

Solution idea

This approach is an optimization of the previous one. When the number of mappings is limited, approach 3 looks good. The critical questions are: What if we need to add too many mappings? What if we need to change the mapping or maybe delete a mapping? Are we going to change the code whenever we have a modification in mappings? So one idea is clear: Having a condition for every mapping is not feasible, or the code might be difficult to maintain.

One idea is to insert all given mappings into a Hash Table in the form of key-value pairs. Here, the number is the key, and the desired output string is the value. For every number i = 1 to n, we go through every entry in the hash table. If the number is divisible by a key, we concatenate the corresponding hash value to the output string for the current number. This way, we can insert or delete mappings from the hash table without changing the code.

Solution steps

Step 1: We insert all mappings in a hash table. For the FizzBuzz problem, the hash table would look something like { (3, 'Fizz'), (5, 'Buzz') }. Similarly, for the FizzBuzzJazz problem, the hash table would look something like { (3, 'Fizz'), (5, 'Buzz'), (7, 'Jazz') }

Step 2: We run a loop from i = 1 to n. For every number i, we iterate over the hash table and check for divisibility with each key. If the number is divisible by a key, we concatenate the corresponding hash value to the output[] string.

Step 3: Finally, we add the resulting string to the output[] string.

Solution pseudocode

string[] fizzBuzzGame(int n) 
{
    string output[n]    
    HashTable fizzBuzz
    fizzBuzz.insert(3, "Fizz")
    fizzBuzz.insert(5, "Buzz")
    for (int i = 1; i <= n; i = i + 1)
    {
        string s = ""
        for (all keys in the hash table fizzBizz)
        {
            if ((i % key) == 0)
                s = s + fizzBizz.get(key)
        }
        if (s == "")
            s = s + string value of i
        output[i] = s
    }
    return output
}

Implementation code C++

string* fizzBuzzGame(int n)
{
    string *output = new string[n];
    unordered_map<int, string> fizzBuzz;
    fizzBuzz[3] = "Fizz";
    fizzBuzz[5] = "Buzz";
    for (int i = 1; i <= n; i =  i + 1)
    {
        string s = "";
        for (auto key : fizzBuzz)
        {
             if (i % key.first == 0)
                s = s + fizzBuzz[key.first];
        }
        if (s == "")
            s = s + to_string(i);

        output[i-1] = s;
    }

    return output;
}

Implementation code Python

def fizzBuzzGame(n):
    output = []
    fizz_buzz = {3: "Fizz", 5: "Buzz"}
    for i in range(1, n+1):
        s = ""
        for key in fizz_buzz:
            if i % key == 0:
                s = s + fizz_buzz[key]
        if s == "":
            s = str(i)
        output.append(s)

    return output

Implementation code Java

public class FizzBuzz
{
    public String[] fizzBuzzGame(int n) 
    {
        String[] output = new String[n];
        Map<Integer, String> fizzBuzz = new HashMap<>();
        fizzBuzz.put(3, "Fizz");
        fizzBuzz.put(5, "Buzz");

        for (int i = 1; i <= n; i = i + 1) 
        {
            String s = "";
            for (int key : fizzBuzz.keySet()) 
            {
                if (i % key == 0)
                    s = s + fizzBuzz.get(key);
            }
            if (s.isEmpty())
                s = s + Integer.toString(i);

            output[i-1] = s;
        }

        return output;
    }
}

Solution analysis

The size of the hash table will be constant because we are storing a constant number of key-value pairs. Space complexity = O(1). At each iteration of the outer loop, we will be doing a constant number of operations. Time complexity = O(n)*O(1) = O(n).

Critical ideas to think!

• How will the time and space complexity of the above approaches change when integer-to-string mapping increases in the problem?
• In approach 1, can we check the divisibility by 15 to print the "FizzBuzz" instead of checking the divisibility by both 3 and 5?
• Can we come up with some other approaches to solve this problem?
• The hash table works as an unordered dictionary which does not preserve the order of keys. Can we use the ordered dictionary or BST to solve this problem? What would be the time complexity? Is it better than the hash table approach?
• Instead of the hash table, can we use the ordered list of (divisor, string)?
• Explore the library implementation of dictionaries in various programming languages. Do they have some extra capabilities to preserve the insertion order of elements?
• Explore the several variations of the FizzBuzz problem.
• Just for fun :) Write the worst but the working implementation of Fizz Buzz that you can think of!

Please write in the message below if you want to share more insight, or if you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!