Difficulty: Easy, Asked-In: Google, Microsoft, Amazon
Key takeaway: FizzBuzz game is a popular problem that is more about learning the basic programming concepts such as if-else, loops, string operations, mathematical operations, optimizations, etc.
This game is played in a group, where players take turns to say the next number in a sequence, counting one at a time.
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:
Important note: Before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!
Input: n = 15
Output: ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz"]
The most basic solution is to run a loop from 1 to n and use modulus operation. In this loop, we use 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 ith index in output[] string. Once loop has been completed, we return output[] string.
// 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;
}
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
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;
}
}
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).
Note: The above code works perfectly but there are some limitations:
Now critical question is: How do we think to solve fizz buzz problem without using mod operation? Let's think!
When we explore each number from the start, word "Fizz" will appear after the cycle of 3. Similarly, word "Buzz" will appear after the cycle of 5. Then what would be the scenario when both words come together? The answer is simple: "FizzBuzz" will appear after the cycle of 15 because 15 is the lowest number which is divisible by both 3 and 5. Think!
So using the above insight, let's track the appearance cycle of the words "Fizz" and "Buzz using two variables fizzCount and buzzCount. In start, we initialize both variables with 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 cycle of 3 and 5.
Now there would be four scenarios:
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;
}
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
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;
}
}
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).
In the above solution, we are still using a lot of conditional statements. Now critical question is: Can we reduce number of conditional statements in the loop? Let's think!
For example, if 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:
If FizzBuzz mappings will increase further, 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.
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:
Step 3: Once the loop is over, we return the output[] string as an output.
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;
}
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
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;
}
}
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).
This approach is an optimization over previous approach. When 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 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 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 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 number is divisible by key, we concatenate corresponding hash value to output string for the current number. This way, we can insert or delete mappings from hash table without changing the code.
Step 1: We insert all mappings in a hash table. For FizzBuzz problem, hash table would look something like { (3, 'Fizz'), (5, 'Buzz') }. Similarly, for FizzBuzzJazz problem, 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 hash table and check for divisibility with each key. If number is divisible by key, we concatenate corresponding hash value to output[] string.
Step 3: Finally, we add resulting string to output[] string.
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
}
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;
}
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
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;
}
}
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).
Please write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!