Which FizzBuzz solution is the most efficient?

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:

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:

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:

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:

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:

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):

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 .