412. Fizz Buzz
Problem Description
The problem "FizzBuzz" is a classic example often used in coding interviews to assess basic programming abilities. Given a positive integer n
, the task is to construct an array of strings that follow a specific pattern based on whether the index of the array (starting from 1) is divisible by 3, 5, or both:
- For each index 'i' that is divisible by both 3 and 5 (for example, 15, 30, 45), the array should contain the string "FizzBuzz" at that index.
- If the index 'i' is only divisible by 3 (like 3, 6, 9), the array should have "Fizz" at that index.
- If the index 'i' is only divisible by 5 (such as 5, 10, 20), the string "Buzz" should appear at that index.
- For all other indexes that don't meet the above divisibility conditions, the array should store the index 'i' itself as a string.
The function should return the array, which is described as answer
, and it should be 1-indexed, meaning the first element corresponds to i=1
.
Intuition
The solution is straightforward ā it systematically checks each number from 1 to n
against the divisibility rules provided in the problem statement. The process can be summarized as follows:
- Iterate over the range from 1 to
n
(inclusive), representing the index 'i'. - For each 'i', examine the remainder when 'i' is divided by 3, 5, and the least common multiple of 3 and 5 (which is 15), to determine divisibility.
- If 'i' is divisible by 15, it means it's divisible by both 3 and 5, so append the string "FizzBuzz" to the answer list.
- Otherwise, if 'i' is divisible by just 3, append "Fizz".
- Otherwise, if 'i' is divisible by just 5, append "Buzz".
- If none of these conditions match, convert 'i' to a string and append it to the answer list.
This logic utilizes the properties of divisibility and the observation that any number divisible by both 3 and 5 is also divisible by 15, allowing for a clean and organized check without further complication or redundant conditions.
Learn more about Math patterns.
Solution Approach
The implementation of the solution for the FizzBuzz problem uses a simple for-loop and basic control statements (if-elif-else). Here's how each part of the code contributes to the solution:
-
Data Structure: A list
ans
is used to collect the results. Lists in Python are dynamic arrays that can grow as needed, which is perfect for this use case since we initially don't know how many "Fizz", "Buzz", or "FizzBuzz" entries we will have. -
Algorithm:
- A for-loop iterates over the range of numbers from 1 to
n
(inclusive), which directly translates to the 1-indexed array requirement of the problem. - Inside the loop, the first condition checked is
if i % 15 == 0
:- The use of 15 is a result of recognizing that 15 is the least common multiple (LCM) of 3 and 5, so any number divisible by both 3 and 5 is divisible by 15.
- If this condition is true, "FizzBuzz" is appended to
ans
.
- The
elif
conditionsi % 3 == 0
andi % 5 == 0
follow:- These conditions use the modulus operator
%
to check for divisibility by 3 or 5, respectively. - If
i
meets either condition, "Fizz" or "Buzz" is appended toans
.
- These conditions use the modulus operator
- The
else
case handles numbers not divisible by 3 or 5 by converting the numberi
to a string usingstr(i)
and appending it toans
.
- A for-loop iterates over the range of numbers from 1 to
-
Code Complexity:
- Time complexity: O(n), where
n
is the input number. Each number up ton
is checked exactly once. - Space complexity: O(n), since a list of
n
strings is being constructed to store the results.
- Time complexity: O(n), where
-
Patterns Used:
- The implementation demonstrates the use of modulo arithmetic to check for divisibility, a typical pattern when handling such conditions.
- Following a sequential pattern, checking the most stringent condition first (divisibility by both 3 and 5) simplifies the logic and prevents redundant checks.
By adhering to the outlines provided in the problem statement, the solution methodically constructs the required FizzBuzz sequence in the form of a list of strings.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through each step of the FizzBuzz problem solution using the example where n
is 16. This will demonstrate how the algorithm works by iterating through each number from 1 to 16 and deciding what to append to the answer list.
-
Initialization: Create an empty list
ans
to store the results. -
Iteration: Use a for-loop to iterate through numbers from 1 to 16 (inclusive). These numbers represent the index 'i'.
- When
i = 1
, none of the special conditions are met, so "1" is appended toans
. - When
i = 2
, similarly toi = 1
, it does not meet any of the special conditions; "2" is appended.
- When
-
Divisibility Check:
- For
i = 3
,i
is divisible by 3. Since3 % 3 == 0
and3 % 15 != 0
, "Fizz" is appended toans
. - For
i = 4
, it is neither divisible by 3 nor 5; thus, "4" is appended. - For
i = 5
,i
is divisible by 5. Since5 % 5 == 0
and5 % 15 != 0
, "Buzz" is appended. - This process continues until
i = 15
, where special case for "FizzBuzz" is encountered because15 % 15 == 0
. - Lastly,
i = 16
is another number that does not meet any special conditions, so "16" is appended.
- For
-
Constructing Final Output: As the loop finishes, the
ans
list looks like this:["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz", "16"]
.
Every other number from 1 to 16 checks each if-elif-else condition in the algorithm to determine the correct string to append. By the end of the loop, we get the complete FizzBuzz pattern up to the number 16.
- Return Result:
The function will return the
ans
list containing the final sequence adhering to the FizzBuzz rules forn = 16
.
By closely adhering to the proposed solution approach, the FizzBuzz sequence is created with efficient checks for divisibility and by appending the correct responses to a dynamically growing list that is structured as per the problem requirements.
Solution Implementation
1from typing import List
2
3class Solution:
4 def fizzBuzz(self, n: int) -> List[str]:
5 # Initialize an empty list to hold the results
6 results = []
7
8 # Loop through numbers from 1 to n
9 for number in range(1, n + 1):
10 # If number is divisible by both 3 and 5 (or 15)
11 if number % 15 == 0:
12 results.append('FizzBuzz')
13 # If number is only divisible by 3
14 elif number % 3 == 0:
15 results.append('Fizz')
16 # If number is only divisible by 5
17 elif number % 5 == 0:
18 results.append('Buzz')
19 # If number is not divisible by either 3 or 5
20 else:
21 results.append(str(number))
22
23 # Return the list containing the FizzBuzz results
24 return results
25
1import java.util.List;
2import java.util.ArrayList;
3
4class Solution {
5 /**
6 * Generates a list of strings representing the FizzBuzz sequence up to n.
7 *
8 * @param n The number up to which the FizzBuzz sequence should be generated.
9 * @return A list of strings corresponding to the FizzBuzz sequence.
10 */
11 public List<String> fizzBuzz(int n) {
12 // Initialize an ArrayList to hold the FizzBuzz results
13 List<String> answer = new ArrayList<>();
14
15 // Loop through numbers from 1 to n
16 for (int num = 1; num <= n; ++num) {
17 // Initialize an empty string to hold the current answer
18 String current = "";
19
20 // Check if the number is divisible by 3 and append "Fizz" if it is
21 if (num % 3 == 0) {
22 current += "Fizz";
23 }
24
25 // Check if the number is divisible by 5 and append "Buzz" if it is
26 if (num % 5 == 0) {
27 current += "Buzz";
28 }
29
30 // If the string is still empty, the number is neither divisible by 3 nor 5
31 // Convert the number to string and use it as the current answer
32 if (current.isEmpty()) {
33 current += Integer.toString(num);
34 }
35
36 // Add the current answer to the list
37 answer.add(current);
38 }
39
40 // Return the complete list of FizzBuzz results
41 return answer;
42 }
43}
44
1#include <vector>
2#include <string>
3
4class Solution {
5public:
6 // Function to solve the FizzBuzz problem
7 std::vector<std::string> fizzBuzz(int n) {
8 // Initialize an empty vector of strings to store the result
9 std::vector<std::string> result;
10
11 // Loop from 1 to n
12 for (int i = 1; i <= n; ++i) {
13 // Initialize an empty string for the current element
14 std::string element;
15
16 // If i is divisible by 3, append "Fizz" to the element string
17 if (i % 3 == 0) {
18 element += "Fizz";
19 }
20
21 // If i is divisible by 5, append "Buzz" to the element string
22 if (i % 5 == 0) {
23 element += "Buzz";
24 }
25
26 // If the element string is still empty, it's neither divisible by 3 nor 5
27 // Convert the number to string and use that as the element
28 if (element.empty()) {
29 element = std::to_string(i);
30 }
31
32 // Add the element string to the result vector
33 result.push_back(element);
34 }
35
36 // Return the final result vector
37 return result;
38 }
39};
40
1// Type annotation for the function parameter
2const fizzBuzz = function (n: number): string[] {
3 // Explicitly define type for the array that will hold the FizzBuzz string sequence
4 let sequence: string[] = [];
5
6 // Iterate from 1 to n
7 for (let i = 1; i <= n; i++) {
8 // If the current number i is divisible by 15, add "FizzBuzz"
9 if (i % 15 === 0) sequence.push('FizzBuzz');
10 // If the current number i is divisible by 3, add "Fizz"
11 else if (i % 3 === 0) sequence.push('Fizz');
12 // If the current number i is divisible by 5, add "Buzz"
13 else if (i % 5 === 0) sequence.push('Buzz');
14 // Otherwise, add the number as a string
15 else sequence.push(i.toString());
16 }
17
18 // Return the array containing the FizzBuzz sequence
19 return sequence;
20};
21
Time and Space Complexity
Time Complexity
The given code loops through the numbers from 1 to n
, performing a constant amount of work for each number. This results in a time complexity of O(n)
, where n
is the input number to the fizzBuzz
function.
Space Complexity
The space complexity of the function is primarily dictated by the output list ans
. Since the list ans
will contain exactly n
strings, the space complexity of the code is O(n)
, reflecting the space required to store the output.
Learn more about how to find time and space complexity quickly using problem constraints.
Which type of traversal does breadth first search do?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!