# Fizz Buzz Problem

Key takeaway: FizzBuzz is a game that has gained popularity as a programming problem that is more about learning the basic programming concepts such as if-else, loops, string operations, mathematical operations, programming 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 both three and five, the player has to say, “Fizz buzz”.

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 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 non of the above conditions are true.

Example

Intput: n = 15

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

### Discussed solution approaches

• Solution approach 1: Using modulus operation
• Solution approach 2: without using modulus operations
• Solution approach 3: Using string concatenation
• Solution approach 4: using the hash table

### Solution approach 1: Using modulus operation

The most basic solution is of solving the FizzBuzz problem is to loop from 1 to n and use modulus operation. In this loop, we use a set 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 as an output.

Solution Steps

1. Initialize an empty output string.
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 string "FizzBuzz" at the 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.

Solution Pseudocode

``````string[] fizzBuzzGame(int n)
{
string output[n]
for (int i = 1; i <= n; i = i + 1)
{

if ((i % 3 == 0) && (i % 5 == 0))
output[i] = "FizzBuzz"

else if ((i%3) == 0)
output[i] = "Fizz"

else if ((i%5) == 0)
output[i] = "Buzz"

else
output[i] = string.valueOf(i))
}
return output
}
``````

Time and space complexity analysis

• Time complexity = O(n)
• Space complexity = O(1)

This code works perfectly but it has a few limitations:

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

### Solution approach 2: without using modulus operations

Here are the steps to solve the problem without using modulus operation:

1. Initialize two count variables, say fizzCount and buzzCount, to store the count of numbers divisible by 3 and 5, respectively.
2. Run a loop from i = 1 to n and perform the following steps at each iteration:

• Increment fizzCount and buzzCount by 1.
• If fizzCount is equal to 3, print “Fizz” and set fizzCount = 0.
• If buzzCount is equal to 5, print “Buzz” and set buzzCount = 0.
• Similarly, if fizzCount is equal to 3 and buzzCount is equal to 5, store “FizzBuzz” and set both buzzCount and fizzCount equal to 0.
• If the above conditions are not true, then store the string value if integer i.
3. by end of the loop, return the array output[] string.

Solution Pseudocode

``````string[] fizzBuzzGame(int n)
{
string output[n]
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[i] = "FizzBuzz"
fizzCount = 0
buzzCount = 0
}

else if(fizzCount == 3)
{
output[i] = "Fizz"
fizzCount = 0
}

else if(buzzCount == 5)
{
output[i] = "Buzz"
buzzCount = 0
}

else
output[i] = string.valueOf(i)
}
return output
}
``````

Time and space complexity analysis

• Time complexity = O(n)
• Space complexity = O(1)

### Solution approach 3: Using string concatenation

Solution Idea

Now a critical question is: is it possible to reduce the number of conditional statements in the loop? Let's think!

This approach will not reduce the time complexity but provide a clean solution when FizzBuzz comes with a twist. 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 solve this with the previous approach, then we need to check several 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.

So if the FizzBuzz mappings increase, the number of conditional statements would grow exponentially in your program. So one idea is: instead of checking for every possible combination of these conditional statements, we check for divisibility by given numbers in the problem i.e. 3, 5. If the number is divisible, we concatenate the corresponding string mapping "Fizz" or "Buzz" to the output[] string.

So for FizzBuzz, we just check for two conditions instead of three conditions as in the first approach. Similarly, for FizzBuzzJazz, now we would have three conditions to check for divisibility.

Solution steps

• Here we start by defining the ith index in our output[] string as an empty string s.
• If the integer i is divisible by 3, we add “Fizz” onto the end of the empty string s.
• Similarly, if i is divisible by 3, we add “Buzz” onto the end of the empty string s.
• Finally, we check whether output[i] is empty. If so, we store the string value of integer i in the empty string s.
• Now we store the value of s at the ith index of the output string.
• Once the loop is over, we return the output[] string as an output.

Solution Pseudocode

``````string[] fizzBuzzGame(int n)
{
string output[n]
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 == "")
s = s + string.valueOf(i)

output[i] = s
}
return output
}
``````

Time and space complexity analysis

• Time complexity = O(n)
• Space complexity = O(1)

### Solution approach 4: using a hash table

Solution Idea

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

One idea is to insert all given mappings in a Hash Table in the form of key-value pair. Here the number is the key, and 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 the 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 worrying about changing the code.

Solution steps

• We insert all the 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') }
• Run a loop on the numbers from 1 to n.
• For every number, iterate over the hash table and check for divisibility with each key.
• If the number is divisible by the key, we concatenate the corresponding hash value to the answer string for the current number.
``````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 (Integer key : fizzBizz.keySet())
{
if ((i % key) == 0)
s = s + fizzBizz.get(key)
}

if (s == "")
s = s + String.valueOf(i)

output[i] = s
}
return output
}
``````

Time and space complexity analysis

• Time complexity = O(n)
• Space complexity = O(1)

### Critical ideas to think!

• Analyze the time and space complexity of the above approaches? How will the time and space complexity of the above approaches affect when integer to string mapping in the problem will increase?
• 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 with some other approaches to solve this problem?
• Try to dey run the 2nd approach and understand: how it is working?
• Why is the space complexity of the above approach O(1) if we use the memory of size n to store the output string? Shouldn't it be O(n)?
• Hash table works as an unordered dictionary which doe 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 solve the problem using 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.

Enjoy learning, Enjoy coding!