412. Fizz Buzz - Detailed Explanation
Problem Statement
Given an integer n, return a list of strings that follows these rules:
- For each number from 1 to n, convert the number to a string.
- If the number is divisible by 3, output
"Fizz"instead of the number. - If the number is divisible by 5, output
"Buzz"instead of the number. - If the number is divisible by both 3 and 5, output
"FizzBuzz"instead of the number.
Example
Input: n = 15
Output: ["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz"]
Constraints
1 <= n <= 10^4
Hints to Solve the Problem
- Use the modulo operator (
%) – Check divisibility using expressions likei % 3andi % 5. - Order your conditionals properly – Always check if a number is divisible by both 3 and 5 first, before checking divisibility by each one individually. This ensures that the combined case (“FizzBuzz”) is handled correctly.
Approach 1: Basic Iterative Solution
Explanation
This straightforward approach uses a simple loop and conditional statements:
- Iterate
ifrom 1 ton. - If
iis divisible by both 3 and 5, append "FizzBuzz" to the result list. - Else if
iis divisible by 3, append "Fizz". - Else if
iis divisible by 5, append "Buzz". - Otherwise, convert
ito a string and append it.
Python Code:
Complexity Analysis
- Time Complexity: O(n) – We perform a constant amount of work (the checks and possibly an append) for each number from 1 to n.
- Space Complexity: O(n) – The output list grows linearly with the number of entries (one output string per number).
Java Code:
Approach 2: Optimized String Concatenation
Explanation
This approach reduces the number of conditional branches by building the output string using concatenation:
- Iterate
ifrom 1 to n and start with an empty stringoutputfor each number. - If
iis divisible by 3, append"Fizz"tooutput. - If
iis divisible by 5, append"Buzz"tooutput. - If after these checks
outputis still empty (meaningiwas not divisible by 3 or 5), then setoutputto the numberi(as a string). - Append
outputto the result list.
Python Code:
Complexity Analysis
- Time Complexity: O(n) – We still process each number once, with a constant amount of work (checks and string appends).
- Space Complexity: O(n) – We store the result for each of the n numbers.
Java Code:
Edge Cases
-
Smallest input (n = 1): The output should simply be
["1"]because no Fizz or Buzz replacements occur. -
Only one type of replacement: For example, if
n = 5, the output should be["1", "2", "Fizz", "4", "Buzz"]. This checks that multiples of 3 and 5 are handled correctly in isolation. -
Large input (n = 10000): Ensure that your solution runs efficiently for the upper constraint. The approaches above handle up to 10,000 iterations easily within time limits.
Common Mistakes
- Wrong order of checks: Checking for divisibility by 3 or 5 before checking for 3 and 5 can lead to missing the "FizzBuzz" case. Always handle the combined case first, or use an approach (like string concatenation) that inherently covers it.
- Not converting to string: Forgetting to convert the number to a string when it doesn't meet any Fizz/Buzz conditions will result in a type error or incorrect output format.
Related Problems
- Fizz Buzz Variations: Variations of the FizzBuzz problem that use different divisors or replacement words.
- Replace Elements in a List: General problems where certain elements in a list are replaced based on a rule (similar idea of scanning and conditionally modifying output).
- Modulo-based String Transformations: Tasks that involve transforming numbers into strings based on their properties (often using the modulo operation as the key check).
These approaches cover both basic and optimized solutions for FizzBuzz while keeping the time and space complexity linear. With this understanding, you can confidently solve the FizzBuzz problem in any programming language.
GET YOUR FREE
Coding Questions Catalog
