Fizz Buzz
EasyPrompt
Given an integer n, return a string array answer (1-indexed) where:
answer[i] == "FizzBuzz"ifiis divisible by3and5.answer[i] == "Fizz"ifiis divisible by3.answer[i] == "Buzz"ifiis divisible by5.answer[i] == i(as a string) if none of the above conditions are true.
Example 1:
Input: n = 3
Output: ["1","2","Fizz"]Example 2:
Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]Example 3:
Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]
Constraints:
1 <= n <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a hash map to store the divisibility rules. It's the most flexible and scalable solution, as new rules can be added just by modifying the map. The code iterates through the numbers from 1 to n, and for each number, it checks against all the rules in the map to build the corresponding string.
Algorithm
- Create a map (e.g.,
LinkedHashMapto preserve order) to store divisor-string pairs (e.g., 3 -> "Fizz", 5 -> "Buzz"). - Initialize an empty list for the results.
- Loop from
i = 1ton. - For each
i, initialize an emptyStringBuilder. - Iterate through the map's entries. If
iis divisible by the entry's key, append the entry's value to theStringBuilder. - If the
StringBuilderis empty after checking all rules, append the numberi. - Add the
StringBuilder's content to the result list. - Return the result list.
Walkthrough
This is the most scalable and generic approach. We store the divisibility rules in a data structure, like a hash map. The main loop then iterates through these rules to build the output string. This decouples the rules from the processing logic, making the code very clean and easy to extend without modification.
import java.util.ArrayList;import java.util.LinkedHashMap;import java.util.List;import java.util.Map; class Solution { public List<String> fizzBuzz(int n) { List<String> answer = new ArrayList<>(); // Using LinkedHashMap to maintain insertion order ("Fizz" before "Buzz") Map<Integer, String> fizzBuzzMap = new LinkedHashMap<>(); fizzBuzzMap.put(3, "Fizz"); fizzBuzzMap.put(5, "Buzz"); for (int i = 1; i <= n; i++) { StringBuilder currentString = new StringBuilder(); for (Integer key : fizzBuzzMap.keySet()) { if (i % key == 0) { currentString.append(fizzBuzzMap.get(key)); } } if (currentString.length() == 0) { currentString.append(i); } answer.add(currentString.toString()); } return answer; }}Complexity
Time
O(n * k), where n is the input number and k is the number of divisibility rules. Since k is a small constant, this is effectively O(n), but it has more overhead than hardcoded solutions.
Space
O(n) to store the output array. An additional O(k) space is used for the map, where k is the number of rules.
Trade-offs
Pros
Highly flexible and scalable.
Follows the Open/Closed Principle, as new rules can be added without modifying the core logic.
Cons
Slightly more complex to implement than simpler approaches.
Has a higher constant factor for time complexity, making it potentially slower for this specific problem with few rules.
This approach avoids a rigid if-else-if structure by building the result string conditionally. It checks for divisibility by 3 and 5 independently and concatenates 'Fizz' and 'Buzz' as needed. This makes the code more modular and cleanly handles the 'FizzBuzz' case without a separate check.
Algorithm
- Initialize an empty list for the results.
- Loop from
i = 1ton. - For each
i, initialize an emptyStringBuilder. - If
iis divisible by 3, append "Fizz". - If
iis divisible by 5, append "Buzz". - If the
StringBuilderis still empty, append the numberi. - Add the
StringBuilder's content to the result list. - Return the result list.
Walkthrough
This approach improves upon the rigidity of the if-else chain. Instead of mutually exclusive conditions, we build the result string piece by piece. This makes the code more modular and easier to extend.
import java.util.ArrayList;import java.util.List; class Solution { public List<String> fizzBuzz(int n) { List<String> answer = new ArrayList<>(); for (int i = 1; i <= n; i++) { StringBuilder currentString = new StringBuilder(); if (i % 3 == 0) { currentString.append("Fizz"); } if (i % 5 == 0) { currentString.append("Buzz"); } if (currentString.length() == 0) { currentString.append(i); } answer.add(currentString.toString()); } return answer; }}Complexity
Time
O(n), as we iterate from 1 to n once. Each number involves a constant number of checks and operations.
Space
O(n) to store the output array.
Trade-offs
Pros
More flexible than a rigid if-else chain.
Handles combined conditions (like 'FizzBuzz') elegantly without an explicit combined check.
Cons
Performs two modulo operations for every number, which might be slightly less performant than an optimized conditional check in some cases.
This is the most direct and computationally efficient approach for the given problem constraints. It uses a simple loop and an if-else-if ladder. By checking for the most specific condition first (divisibility by 15 for 'FizzBuzz'), we minimize the number of checks required on average.
Algorithm
- Initialize an empty list for the results.
- Loop from
i = 1ton. - If
iis divisible by 15 (i % 15 == 0), add "FizzBuzz". - Else if
iis divisible by 3 (i % 3 == 0), add "Fizz". - Else if
iis divisible by 5 (i % 5 == 0), add "Buzz". - Else, add the string representation of
i. - Add the chosen string to the result list.
- Return the result list.
Walkthrough
This is the most straightforward approach. We iterate from 1 to n. In each iteration, we use a chain of if-else if-else statements to check for divisibility. The order of checks is important for both correctness and efficiency. We must check for divisibility by 15 first, before checking for divisibility by 3 or 5 individually, to ensure the correct output and minimize operations.
import java.util.ArrayList;import java.util.List; class Solution { public List<String> fizzBuzz(int n) { List<String> answer = new ArrayList<>(); for (int i = 1; i <= n; i++) { if (i % 15 == 0) { answer.add("FizzBuzz"); } else if (i % 3 == 0) { answer.add("Fizz"); } else if (i % 5 == 0) { answer.add("Buzz"); } else { answer.add(String.valueOf(i)); } } return answer; }}Complexity
Time
O(n). This approach is highly efficient as it iterates through the numbers once and performs a minimal number of modulo operations on average.
Space
O(n) to store the output array.
Trade-offs
Pros
Simple to understand and implement.
Most performant in terms of raw computation due to optimized condition ordering.
Cons
The logic is rigid and not easily extensible. Adding a new rule requires modifying the entire conditional structure.
Solutions
Solution
const fizzBuzz = function ( n ) { let arr = []; for ( let i = 1 ; i <= n ; i ++ ) { if ( i % 15 === 0 ) arr . push ( ' FizzBuzz ' ); else if ( i % 3 === 0 ) arr . push ( ' Fizz ' ); else if ( i % 5 === 0 ) arr . push ( ' Buzz ' ); else arr . push ( ` ${ i } ` ); } return arr ; };class Solution {public List<String> fizzBuzz(int n) { List<String> ans = new ArrayList<>(); for (int i = 1; i <= n; ++i) { String s = ""; if (i % 3 == 0) { s += "Fizz"; } if (i % 5 == 0) { s += "Buzz"; } if (s.length() == 0) { s += i; } ans.add(s); } return ans; }}class Solution {public: vector<string> fizzBuzz(int n) { vector<string> ans; for (int i = 1; i <= n; ++i) { string s = ""; if (i % 3 == 0) s += "Fizz"; if (i % 5 == 0) s += "Buzz"; if (s.size() == 0) s = to_string(i); ans.push_back(s); } return ans; }};class Solution: def fizzBuzz(self, n: int) -> List[str]: ans = [] for i in range(1, n + 1): if i % 15 == 0: ans . append('FizzBuzz') elif i % 3 == 0: ans . append('Fizz') elif i % 5 == 0: ans . append('Buzz') else: ans . append(str(i)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.