FizzBuzz Analysis

Recently I was asked this kind of question. As I was told not to worry too much about it and I got many other questions to answer within short time, I did not pay attention to much on it and just scribbled it on a piece of paper, no time to mentally test the algorithm.

At home I realized I did not complete the answer (blame that to the recruiter).  Anyway, the fizz buzz interview question is to ask interviewee to write a code to print number from 1 to 100, but for every multiplication of 3 to print string "FIZZ" (or something), for every multiplication of 5 to print string "BUZZ", and for every multiplication of 3 and 5 (which is another way to say multiplication of 15) to print "FIZZBUZZ".

Here's my working code in C++:

#include <iostream>

using namespace std;

const static char *s1 = "FIZZ";
const static char *s2 = "BUZZ";

int main()
{
    for(int i=1; i<=100; i++)
    {
        if (i% 3*5==0)
        {
            cout << s1 << s2 << endl;
            continue;
        }
        if (i % 3 == 0)
        {
            cout << s1 << endl;
            continue;
        }
        if (i % 5 == 0)
        {
            cout << s2 << endl;
            continue;
        }

        cout << i << endl;
    }
}

No matter whay you do, the optimal solution is always O(n) (unless you're crazy enough to just print manually without loop, such as cout << "1\n2\FIZZ\n4\BUZZ\n...|").

Some silly optimization can be performed in printing the string, though.

#include <iostream>

using namespace std;

const static string s = "FizzBuzz";

int main()

{

    for(int i=1; i<=100; i++)

    {

        if (i%15==0)

        {

            cout << s << endl;

            continue;

        }

        if (i % 3 == 0)

        {

            cout << s.substr(0,3) << endl;

            continue;

        }

        if (i % 5 == 0)

        {

            cout << s.substr(4) << endl;

            continue;

        }

        cout << i << endl;

    }

}

Another thought is to eliminate mod 15.  For example:

#include <iostream>

using namespace std;

const static string s = "FizzBuzz";

int main()

{

    int m;

    for(int i=1; i<=100; i++)

    {

        m = 0;

        if (i%3==0)

        {

            cout << s.substr(0,3);

            m++;

        }

        if (i % 5 == 0)

        {

            cout << s.substr(4);

            m++;

        }

        if (m > 0)

            cout << endl;

        else

            cout << i << endl;

    }

}

When I tested it (upper limit set to 1000 and perform "time <program>", the last algorithm shows some speedup.

The last few lines can be optimized to be:

        if (m == 0)

            cout << i;

        cout << endl;

Another tiny optimization is instead of doing post increment (i++), we do preincrement (++i).  This saves tiny bit (no copy to extra variable internally).

Last, we can write it down in Assembly if we want.  The following is suitable for embedded device:

main:

leal 4(%esp), %ecx

andl    $-16, %esp

pushl -4(%ecx)

pushl %ebp

movl %esp, %ebp

pushl %edi

pushl %esi

pushl %ebx

pushl %ecx

subl $8, %esp

movl $1, %ebx         ; EBX=1

movl $3, %esi         ; ESI=3

movl $5, %edi         ; EDI=5

jmp CHECK_FIZZ

FOR_I_NEXT:

movl %ebx, %eax       ; eax stores current value of i

cltd

idivl %edi             ; i / 5, result in eax and mod in edx

testl %edx, %edx       ; i % 5

jne PRINT_I          ; i % 5 != 0 -> jump to PRINT_I

CHECK_FUZZ:

subl $8, %esp

pushl stdout

pushl 'f'

call _IO_putc

popl %edx

popl %ecx

pushl stdout

pushl 'i'

call _IO_putc

popl %eax

popl %edx

pushl stdout

pushl 'z'

call _IO_putc

popl %ecx

popl %eax

pushl stdout

pushl 'z'

call _IO_putc

addl $16, %esp

PRINT_CR:

subl   $8, %esp

pushl stdout

pushl '\n'

call _IO_putc

incl %ebx

addl $16, %esp

cmpl $101, %ebx           ; i == 101 ?

je MAIN_EXIT            ; if (i ==101) goto MAIN_EXIT

CHECK_FIZZ:

movl %ebx, %eax

cltd

idivl %esi

testl %edx, %edx           ; i % 3 == 0

jne FOR_I_NEXT

subl $8, %esp             ; if (i%3==0):

pushl stdout

pushl 'b'

call _IO_putc

popl %eax

popl %edx

pushl stdout

pushl 'u'

call _IO_putc

popl %ecx

popl %eax

pushl stdout

pushl 'z'

call _IO_putc

popl %eax

popl %edx

pushl stdout

pushl 'z'

call _IO_putc

movl %ebx, %eax

cltd

idivl %edi

addl $16, %esp

testl %edx, %edx

jne PRINT_CR

jmp CHECK_FUZZ

PRINT_I:

pushl %eax

pushl %ebx

pushl $.LC0

pushl $1

call __printf_chk

addl $16, %esp

jmp PRINT_CR

MAIN_EXIT:

xorl   %eax, %eax

leal -16(%ebp), %esp

popl %ecx

popl %ebx

popl %esi

popl %edi

popl %ebp

leal -4(%ecx), %esp

ret