Fizz Buzz Problem

Problem

Given an integer n, return a string array answer (1-indexed) where:

  • answer[i] == "FizzBuzz" if i is divisible by 3 and 5.
  • answer[i] == "Fizz" if i is divisible by 3.
  • answer[i] == "Buzz" if i is divisible by 5.
  • answer[i] == i (as a string) if none of the above conditions are true.

Examples

Example 1:

1
2

Input: n = 3
Output: ["1","2","Fizz"]

Example 2:

1
2

Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]

Example 3:

1
2

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

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

1
2


##### C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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:

1
2
3
4

@FunctionalInterface
interface IntPredicate {
	boolean apply(int i);
}

Now, we can add rules like:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7
8

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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);
    }
}