412. Fizz Buzz

EasyMathStringSimulation

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 conditions i % 3 == 0 and i % 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 to ans.
- The else case handles numbers not divisible by 3 or 5 by converting the number i to a string using str(i) and appending it to ans.
Code Complexity:
- Time complexity: O(n), where n is the input number. Each number up to n is checked exactly once.
- Space complexity: O(n), since a list of n strings is being constructed to store the results.
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 Evaluator

Example 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 to ans.
- When i = 2, similarly to i = 1, it does not meet any of the special conditions; "2" is appended.
Divisibility Check:
- For i = 3, i is divisible by 3. Since 3 % 3 == 0 and 3 % 15 != 0, "Fizz" is appended to ans.
- For i = 4, it is neither divisible by 3 nor 5; thus, "4" is appended.
- For i = 5, i is divisible by 5. Since 5 % 5 == 0 and 5 % 15 != 0, "Buzz" is appended.
- This process continues until i = 15, where special case for "FizzBuzz" is encountered because 15 % 15 == 0.
- Lastly, i = 16 is another number that does not meet any special conditions, so "16" is appended.
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 for n = 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know