Fizzbuzz without if statements

February 25, 2024 · 10 min read

beho

A dear friend recently challenged me to write fizzbuzz without if statements. Let's try to build it in JavaScript.

Problem statement

Let's first agree with what we mean by fizzbuzz. Fizzbuzz is an algorithm that prints for each integer number:

"fizz" if it is divisible by 3; or
"buzz" if it is divisible by 5; or
"fizzbuzz" if it is divisible by both 3 and 5; or
the number if none of the above apply.

E.g. for the first ten numbers we would expect an output like this:

1
2
fizz
4
buzz
fizz
7
8
fizz
buzz

By definition fizzbuzz has a lot of conditionality baked in, so can we write fizzbuzz without using an if statement?

Rules

No if statements or equivalent control statements. This includes the ternary operator ? and other similar operators that can control flow like ??, && and ||.

The output space

Since we're dealing with numbers and their divisibilty we might want to see if there are any patterns in the way numbers operate to make the pattern simpler.

Exploring with pen and paper can reveal some intuitions that we should prove. In particular:

Any number divisible by both 3 and 5 is also divisible by 15.
The text outputs of fizzbuzz repeat every 15 numbers.

I'm particularly interested in the second point, let's prove it briefly.

Proof

By definition a number divisble by 3 when its remainder when divided by 3 is 0. The modulo operation x mod n is the remainder when x is divided by n.
For integers a, b, n modulo has the property (a + b) mod n = [(a mod n) + (b mod n)] mod n. So for an integer a, (a + 15) mod 3 = [(a mod 3) + (15 mod 3)] mod 3.
But 15 is divisible by 3 so 15 mod 3 = 0. Also a mod 3 mod 3 = a mod 3.
So (a + 15) mod 3 = a mod 3. That is to say when you add 15 to a number its divisibility by 3 doesn't change.

You can use the same logic for 5 and 15 because they are also divisible by 15. So the outputs "fizz", "buzz" and "fizzbuzz" will repeat every 15 numbers.

For those interested in prove properties like these there is a branch of number theory called modular arithmetic that should be interesting.

Hardcoding 15 outputs

This means we can hardcode the first 15 text values of fizzbuzz. Let's index these by the remainder we get when dividing a number by 15.

const values = [
    "fizzbuzz", // n mod 15 (the remainder when
                // dividing by 15) is 0
    undefined,  // n mod 15 = 1
    undefined,  // n mod 15 = 2
    "fizz",
    undefined,
    "buzz",
    "fizz",
    undefined,
    undefined,
    "fizz"
    "buzz"
    undefined,
    "fizz",
    undefined,
    undefined
];

Then our implementation should divide the number by 15 and see what value is set for the remainder. If it is undefined then print the number.

In javascript the modulo operator is a % b gives us the remainder that is left when dividing a by b. Let's use it.

// we want the value if it is defined
// or fallback to the number n
values[n % 15] ? values[n % 15] : n 

// or equivalently with a more concise operator
values[n % 15] ?? n 

For example to print the first 100 values of fizzbuzz:

for (let i = 1; i < 100; i++) {
  console.log(values[n % 15] ?? v);
}

This is a working implementation of fizzbuzz but it still has the control statement ?? which breaks the rules of our challenge.

Removing the last if

If we want to remove any branching logic then at some point we need to express our logic in a single statement.

For fizzbuzz, at some point we need to chose whether to output a number or a word.

Mixing types can make building the output harder. e.g.

> undefined + ""
'undefined'

> 0 + ""
'0'

Towards a string type

Our output is ultimately a string so we can use the empty string for values that don't apply.

This way when we concatenate the values only the results that are nonempty are used.

// get the word output from the list
const v = values[n % 15];

// if the output is a word use it or set empty string
const wordOutput   = v ? v : "";

// if output is not a word use the value of n as a string
const numberOutput = v ? "" : `${n}`;

console.log(wordOutput + numberOutput);

Our log line is now free of if statements and type incompatibilities. How can we build each variable without an if statement?

Exploiting array concatenation

The method Array.join combines a list of strings into a single string by inserting a separator between elements, e.g. `["a", "b"].join(",") outputs "a,b".

If we have a list of empty strings then ["", ""].join("hello") will output "hello". We can exploit the fact that if the list only has one element or is empty then there is no need to insert the separator.

[].join("hello") // ""
[""].join("hello") // ""
["", ""].join("hello") // "hello"

Exploiting array construction

Since the Array constructor can take a number parameter for its length we can write:

new Array(0).join("hello") // ""
new Array(2).join("hello") // "hello"

We can use this to control whether or not to print a string based on the number we pass to the Array constructor.

Deciding the array length

For better or for worse JavaScript will cast boolean values to 1 or 0 when we use arithemtic operators. This way we can get

// 0 if v is set 2 if values is not set
(v === undefined) * 2

// or casting to a boolean based on whether v is truthy
!v * 2

Bringing it all together

Applying our new hacks we can get:

for (let n = 1; n < 100; n++) {
    const v = values[n % 15];
    console.log(
        new Array(!!v * 2).join(v) +
        new Array( !v * 2).join(n)
    );
}

and here we have fizzbuzz with no if statements!

Compressing our output values

This is fine but there's a bit of redundancy in our values list.

We can extract an array to represent the possible string outputs.

const strings = ["", "fizz", "buzz", "fizzbuzz"];
const values = [
    3, // fizzbuzz
    0, // nothing
    0,
    1, // fizz
    0,
    2, // buzz
    1,
    0,
    0,
    1,
    2,
    0,
    1,
    0,
    0
];

Our values array is now behaving like a mask for all of the outputs of fizzbuzz.

We then look up the value in the mask, check if it is nonzero and then look up the corresponding string.

How big is a value?

Let's see if we can compress it further. Since each value in the mask has 4 possible outcomes it can be expressed in just two bits.

We can express a binary literal in JavaScript by putting 0b in front:

=> 0b00 // nothing
=> 0b01 // fizz
=> 0b10 // buzz
=> 0b11 // fizzbuzz

The first four entries in our values list are:

in decimal     3,    0,    0,    1
in binary     11,   00,   00,   01

Using a bitmap

We can join these together to build a bitmap - one binary number that represents the whole list. Building from the right-hand side:

0b01000011
   ^ ^ ^ ^
   1 0 0 3

To get back from this binary representation to the original number, look up index i in the bitmap:

cut off (bitshift) n blocks of two from the front
- in JavaScript x >> (n * 2)
ignore anything larger than two bits (bitwise comparison with 0b11 or 3)
- in JavaScript x & 0b11

For example to get the output of fizzbuzz for the number 2. We look up the 1st (because we index from zero) value in our bitmap.

// cut off 1 block of two from the front
//   by bit shifting 1 * 2 bits to the right
0b01000011 >> (1 * 2)  => 0b010000

// remove everything but the last two bits
//   by bitwise comparing it to 0b11
0b010000 & 0b11        => 0b00

// this is 0 as expected!

Building the full list

Taking our full values map above we get:

// 0   3   11
// 1   0   00
// 2   0   00
// 3   1   01
// 4   0   00
// 5   2   10
// 6   1   01
// 7   0   00
// 8   0   00
// 9   1   01
// 10  2   10
// 11  0   00
// 12  1   01
// 13  0   00
// 14  0   00

=> 0b000001001001000001100001000011

Lucklily the first 5 digits are 0, so we can drop with them without loss of information and get the even smaller:

const bitmap = 0b1001001000001100001000011;

// or expressed as a decimal number
// to make the code more confusing
const bitmap = 19142723;

Bringing it back together

Applying this logic we can write fizzbuzz as (I'm sorry):

const strings = ["", "fizz", "buzz", "fizzbuzz"];
for (let n = 1; n < 100; n++) {
    const v = (19142723 >> (n % 15) * 2) & 0b11;
    console.log(
        new Array(!v  * 2).join(n) +
        new Array(!!v * 2).join(strings[v])
    );
}

Seeing double

Notice that the representation of a pair of bits fairly closely resembles the text output.

-> number
-> fizz
-> buzz
-> fizzbuzz

Read as a bitmap the first bit encodes whether we say "fizz" and the second bit encodes whether we say "buzz".

Splitting the bitmaps out we get the following. N.B. we removed more unneeded zeroes from the front of buzz:

const fizzmap = 0b1001001001001;
const buzzmap =   0b10000100001;

To check the value we don't need to shift by blocks of two, and we can bitwise compare to 0b1 now.

(fizzmap >> n % 15) & 0b1
(buzzmap >> n % 15) & 0b1

If both fizzmap and buzzmap are both true then "fizz" and "buzz" can be concatenated to "fizzbuzz" without a special case.

Writing this out gives us something that looks like the expression of our business logic in the problem statement.

for (let n = 1; n < 100; n++) {
    const fizz = (0b1001001001001 >> n % 15) & 1;
    const buzz = (  0b10000100001 >> n % 15) & 1;
    console.log(
        new Array(fizz * 2).join("fizz") +
        new Array(buzz * 2).join("buzz") +
        new Array((!(fizz || buzz)) * 2).join(n),
    );
}

This is nice because we can remove the need for dividing n by 15 (assuming that it is computationaly expensive).

Can you rewrite this loop to run in blocks of 15?

Overdone?

We've ended up writing a bitmap to encode division by 3. This seems like overkill:

n % 3 === 0 ?? "fizz"

// or cast by truthy value
!(n % 3) ?? "fizz"

// or expressed in our twisted array logic
new Array(!(n % 3) * 2).join("fizz");

We want to print "fizzbuzz" if n is not divisible by 3 or by 5.

// not divisible by 3 or 5
!(!(n % 3) || !(n % 5))

// or equivalently the remainder is
// positive when dividing by 3 and by 5
= !!(n % 3 && n % 5)

We agreed earlier that && is not allowed. Fortunately in boolean algebra AND behaves like multiplication.

In this case if either remainder is zero they will multiply to zero, so we can write:

!!(n % 3 * n % 5)

Which gives us a slightly less weird looking solution:

for (let n = 1; n < 100; n++) {
    console.log(
        new Array(!(n % 3) * 2).join("fizz") +
        new Array(!(n % 5) * 2).join("buzz") +
        new Array(!!(n % 3 * n % 5) * 2).join(n),
    );
}       

Alternatively since we print the number whenever there are no words to print:

for (let n = 1; n < 100; n++) {
    const fizzbuzz =
        new Array(!(n % 3) * 2).join("fizz") +
        new Array(!(n % 5) * 2).join("buzz");
    console.log(
        fizzbuzz + new Array(!fizzbuzz * 2).join(n)
    );
}       

Conclusion

In our attempt to avoid the use of if statements, we've arrived at a concise expression of fizzbuzz.

Relaxing our original constraint we could imagine implementing fizzbuzz like this:

for (let n = 1; n < 100; n++) {
  const fizzbuzz =
    (n % 3 ? "" : "fizz") +
    (n % 5 ? "" : "buzz");
  console.log(fizzbuzz || n);
}

It's important to remmember that there are more potential sources of branching logic than the control flow structures we normally look out for.

Problem statement​

Rules​

The output space​

Hardcoding 15 outputs​

Removing the last if​

Towards a string type​

Exploiting array concatenation​

Exploiting array construction​

Deciding the array length​

Bringing it all together​

Compressing our output values​

How big is a value?​

Using a bitmap​

Building the full list​

Bringing it back together​

Seeing double​

Overdone?​

Conclusion​