Fizz Buzz Problem
Problem
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.
Examples
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"]
Follow ups
Dont use modulo operator %
What if you can’t use modulo operator? - Refer #Method 3 - No modulo Operator
How will you extend for other prime numbers?
What if we want to add “Guzz” when there is divisibility by 7?
Solution
Consider the sequence of numbers from 1 to 10.
1 2 3 4 5 6 7 8 9 10
“Fizz” and “Buzz” are used to replace numbers that are multiples of 3 and 5, respectively. Specifically, if a number is divisible by 3, replace it with “Fizz”; if it’s divisible by 5, replace it with “Buzz”. If a number is divisible by both 3 and 5, replace it with “Fizz Buzz”. This mimics the classic children’s game “Fizz Buzz”.
Method 1 - Iteration using modulo operator and if condition
To find all the fizz and buzz, we must iterate through the numbers in range [1, n] (note that the range is inclusive) and check which numbers are fizz and which are buzz by using the modulo % operator.
Code
C++
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;
}
};
Go
func fizzBuzz(n int) []string {
var ans []string
for i := 1; i <= n; i++ {
s := &strings.Builder{}
if i%3 == 0 {
s.WriteString("Fizz")
}
if i%5 == 0 {
s.WriteString("Buzz")
}
if s.Len() == 0 {
s.WriteString(strconv.Itoa(i))
}
ans = append(ans, s.String())
}
return ans
}
Java
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;
}
}
PHP
class Solution {
/**
* @param Integer $n
* @return String[]
*/
function fizzBuzz($n) {
$rs = [];
for ($i = 1; $i <= $n; $i++) {
if ($i % 3 != 0 && $i % 5 != 0) {
array_push($rs, strval($i));
} elseif ($i % 3 == 0 && $i % 5 != 0) {
array_push($rs, 'Fizz');
} elseif ($i % 3 != 0 && $i % 5 == 0) {
array_push($rs, 'Buzz');
} else {
array_push($rs, 'FizzBuzz');
}
}
return $rs;
}
}
Python
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 ans
…
Complexity
- Time:
O(n) - Space:
O(1)
Method 2 - Using modulo operator and if else
Note the order if-else condition. We first check divisibility by 15, and then divisibility by 3 and 5.
We can also do i % 3 == 0 && i % 5 == 0 in first if condition, but % by 15 is just 1 call and hence more optimal.
Code
Java
class Solution {
public List<String> fizzBuzz(int n) {
List<String> ans = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) {
ans.add("FizzBuzz");
} else if (i % 3 == 0) {
ans.add("Fizz");
} else if (i % 5 == 0) {
ans.add("Buzz");
} else {
ans.add(String.valueOf(i));
}
}
return ans;
}
}
Complexity
- Time:
O(n) - Space:
O(1)
Method 3 - No modulo Operator
Code
Java
class Solution {
public List<String> fizzBuzz(int n) {
List<String> ans = new ArrayList<>();
int i = 1, fizz = 0, buzz = 0;
while (i <= n) {
fizz++;
buzz++;
if (fizz == 3 && buzz == 5) {
ans.add("FizzBuzz");
fizz = buzz = 0;
} else if (fizz == 3) {
ans.add("Fizz");
fizz = 0;
} else if (buzz == 5) {
ans.add("Buzz");
buzz = 0;
} else {
ans.add(String.valueOf(i));
}
i++;
}
return ans;
}
}
Method 4 - Using Ternary Operator
Code
Java
class Solution {
public List fizzBuzz(int n) {
List ans = new ArrayList<>();
for(int i = 1; i <= n; i++){
ans.add(
i % 15 == 0 ? "FizzBuzz" :
i % 5 == 0 ? "Buzz" :
i % 3 == 0 ? "Fizz" :
String.valueOf(i)
);
}
return ans;
}
}
Method 5 - Using Rule engine
This is for second follow up. How can we support divisibility by other prime numbers? like 7?
This idea is inspired from [junm5’s solution](https://leetcode.com/problems/fizz-buzz/solutions/89936/java-fuzz-buzz-follow-up-no-if-else-and-extendable/, where they use Composite Design Pattern.
We can use functional interface or some equivalent in other programming language, to create Rule predicate interface:
@FunctionalInterface
interface IntPredicate {
boolean apply(int i);
}
Now, we can add rules like:
private Map<Rule, String> rules = new LinkedHashMap();
rules.add(i -> i % (7*5*3) == 0, "FizzBuzzGuzz");
rules.add(i -> i % (7*5) == 0, "BuzzGuzz");
rules.add(i -> i % (7*3) == 0, "FizzGuzz");
rules.add(i -> i % (5*3) == 0, "FizzBuzz");
rules.add(i -> i % (7) == 0, "Guzz");
rules.add(i -> i % (5) == 0, "Buzz");
rules.add(i -> i % (3) == 0, "Fizz");
To get the value we can just do following:
private String getValue(int i) {
for (Rule rule : rules) {
if (rule.apply(i)) {
return rules.get(rule);
}
}
return String.valueOf(i);
}
See the code in action below for original FizzBuzz problem.
Code
Java
class Solution {
private Map<Rule, String> rules = new LinkedHashMap();
public List<String> fizzBuzz(int n) {
// note we are using linkedhashmap
rules.add(i -> i % (5*3) == 0, "FizzBuzz");
rules.add(i -> i % (3) == 0, "Fizz");
rules.add(i -> i % (5) == 0, "Buzz");
List<String> ans = new ArrayList<>();
for (int i = 1; i <= n; ++i) {
ans.add(getValue(i));
}
return ans;
}
private String getValue(int i) {
for (Rule rule : rules) {
if (rule.apply(i)) {
return rules.get(rule);
}
}
return String.valueOf(i);
}
}