This little “poor-developer filter” was discussed and solved many times.

Despite the number of discussions it spur, and the many suggested ways to solve the problem, the question regarding which solution would be the most efficient, remained unclear. Maybe because its original goal was to screen “bad” developers rather than actually solve the problem efficiently or demonstrate creativity. It was also said that during an interview, solving the problem in more efficient less readable manner would disqualify the developer.

The FizzBuzz problem seems so naive and simple to solve, that it becomes an even more intriguing task to optimize it. So I’ve looked around the various suggestions (more than 80 languages!), and isolated the key ways to solve the problem. Then I added a simple timing and below are the results. Which FizzBuzz solution is the most efficient?

It seems that there are 4 main patterns to solve the FizzBuzz problem:

  1. Using modulo and int equality test.
  2. Using modulo and string equality test.
  3. Count 3 and 5 down or up as i progress (testing counts of 3 and 5).
  4. Using some bitwise trickery.

I’m using C# in the implementation example, yet the above methods apply to all languages (possibly languages will deffer being better than others comparing ints vs. comparing strings).

Note that I’m using the + sign to concatenate the strings in my examples, yet a more efficient way in C# will be to use StringBuilder. @Thanks Matt!

As shown below, the most effective methods were the ones with: 1. the least int equality tests, and 2. those using less modulo.

The most efficient? we almost have a tie between the following 3 marked in yellow.

Comparing int values (in loop), using 4 (in loop) modulo operations and chained if..else:

Selec All Code:
1
2
3
4
5
6
7
8
for (int i = 1; i < = N; ++i)
{
    if ((i % 3 == 0) && (i % 5 == 0)) result += "FizzBuzz";
    else if (i % 3 == 0) result += "Fizz";
    else if (i % 5 == 0) result += "Buzz";
    else result += i.ToString();
    result += ", ";
}

Comparing int values, using 2 (in loop) modulo operations and 4 (in loop) int equality tests:

Selec All Code:
1
2
3
4
5
6
7
8
for (int i = 1; i < = N; ++i) {
    f = i % 3;
    b = i % 5;
    if(f == 0) result += "Fizz";
    if(b == 0) result += "Buzz"; 
    if (f > 0 && b > 0) result += i.ToString();
    result += ", ";
}

Comparing strings, using 2 (in loop) modulo operations:

Selec All Code:
1
2
3
4
5
6
7
8
for (int i = 1; i < = N; ++i)
{
    outp = "";
    if (i % 3 == 0) outp = "Fizz";
    if (i % 5 == 0) outp += "Buzz";
    if (outp == "") outp = i.ToString();
    result += outp + ", ";
}

Counting up, using 2 single (out of loop) modulo operations:

Selec All Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int x = 3;
int y = 5;
int a = 1;
b = N;
int x1 = a % x;
int y1 = a % y;
result = "";
for (int i = a; i < = b; i++)
{
    if (x1 == 0) result += "Fizz";
    if (y1 == 0) result += "Buzz";
    if (x1 != 0 && y1 != 0) result += i.ToString();
    result += ", ";
    x1 = (x1 == x - 1 ? 0 : x1 + 1);
    y1 = (y1 == y - 1 ? 0 : y1 + 1);
}

Counting down, using no modulo operations, chained if..else:

Selec All 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
int fizz = 3;
int buzz = 5;
for(int i = 1; i < = N; ++i) {
	fizz--;
	buzz--;
    if (fizz == 0 && buzz == 0)
    {
		outp = "FizzBuzz";
		fizz = 3;
		buzz = 5;
    }
    else if (fizz == 0)
    {
		outp = "Fizz";
		fizz = 3;
    }
    else if (buzz == 0)
    {
		outp = "Buzz";
		buzz = 5;
	} else {
		outp = i.ToString();
	}
	result += outp + ", ";
}

All Bitwise operations (using predefined 0-15 numbers mask):

Selec All Code:
1
2
3
4
5
6
7
8
string[] messages = new string[]{null, "Fizz", "Buzz", "FizzBuzz"};
int acc = 810092048; //11 00 00 01 00 10 01 00 00 01 10 00 01 00 00
int c = 0;
for (int i=1; i < = N; ++i)  {
    c = acc & 3;
    result += (c > 0 ? messages[c] : i.ToString()) + ", ";
    acc = acc >> 2 | c < < 28;
}

@Download the full C# code

 

Can you find a more efficient way?

For more exploration, visit this discussion: http://c2.com/cgi/wiki?FizzBuzzTest .

 

 

 

  • Matt Johnson

    Well, since you said this is all c# and you are going for efficiency, you really should get rid of the string concatenation += operators.  Use a StringBuilder, or Console.WriteLine each string directly.  Using string concatenation in a loop is a big performance problem because it allocates new memory on the heap each time you use it.  In other words, s += “foo” needs three separate memory locations (the original value of s, the value of “foo” and the new value of the result).

  • You’re right… thanks for the comment!
    For reference, I’ve added a note to the post.

  • Guest

    As Matt mentioned , the string concatination is the real bottleneck. The solutions are all pretty similar in performance and only differ by the number of result+= statements they use which is why the bitwise version appears faster.

  • lavaeagle

    Just for kicksI wrote this as ternary statements in PHP in one line.  Basically unreadable but funny.

    http://devrabb.it/paste/2T

  • jim ji

    if N is a const number, print the result directly is the most efficient way:)

    like this:

    // N is 100.
    print(“1n2nFizzn4nBuzznFizzn7n8nFizznBuzzn11nFizzn13n14nFizzBuzzn16n17nFizzn19nBuzznFizzn22n23nFizznBuzzn26nFizzn28n29nFizzBuzzn31n32nFizzn34nBuzznFizzn37n38nFizznBuzzn41nFizzn43n44nFizzBuzzn46n47nFizzn49nBuzznFizzn52n53nFizznBuzzn56nFizzn58n59nFizzBuzzn61n62nFizzn64nBuzznFizzn67n68nFizznBuzzn71nFizzn73n74nFizzBuzzn76n77nFizzn79nBuzznFizzn82n83nFizznBuzzn86nFizzn88n89nFizzBuzzn91n92nFizzn94nBuzznFizzn97n98nFizznBuzzn”);

  • Pingback: The Complete Guide to Nailing Your Next Interview()

  • trevdak

    jim.ji is correct you can’t be a straight-up print.
    While we’re at it though, you can eliminate a lot of the math and if statements except for a bit right at the start, and allow for any N:

    We know that the pattern repeats for every 15 n. So why not just determine the length, then print the repeating string until you get to the necessary length?

  • Eren Yavuz

    private static Dictionary Rules { get; } =
    new Dictionary { { 3, “Fizz” }, { 5, “Buzz” } };

    private static string Convert(int i)
    {
    var stringBuilder = new StringBuilder();

    foreach (var rule in Rules) if (i % rule.Key == 0) stringBuilder.Append(rule.Value);

    return string.IsNullOrEmpty(stringBuilder.ToString()) ? i.ToString() : stringBuilder.ToString();
    }

    private static void Main()
    {
    Print(1, 20);

    Console.ReadKey();
    }

    private static void Print(int start, int count)
    {
    var collection = Enumerable.Range(start, count).Select(Convert);

    Console.WriteLine(string.Join(Environment.NewLine, collection));
    }