The FizzBuzz problem

There is a very popular problem around the space known as the FizzBuzz problem. In this problem what we have to do is we have to loop through 1 to n. and wherever we encounter an integer divisible by 3 we need to print Fizz, And whenever we encounter an integer divisible by 5 we need to print Buzz & and “FizzBuzz” if an integer is divisible by both 3 and 5. FizzBuzz is a very simple programming task, used in software developer job interviews, to determine whether the job candidate can actually write code. It was invented by Imran Ghory, and popularized by Jeff Atwood.

So what makes it a good problem...

That is if the programmer writes

def FizzBuzz():
    for i in range(1, 100):
        if i == 0:
            continue
        elif i % 15 == 0:
            print('FizzBuzz')
        elif i % 5 == 0:
            print('Buzz')
        elif i % 3 == 0:
            print('Fizz')
        else:
            print(i)

This does the job of printing the solution. But here is a catch...

The Modulo operator (%) is a heavy operator & works in a different way. if we are saying i % 15 it will denote it as i % 5 && i % 3. Hence, if we are performing i % 15 in the FizzBuzz program we are performing the i % 5 operation twice.

So to deal with this some programmers approach this problem in a different way.

Their approach is

def FizzBuzz():
    f = False
    d = ""
    for i in range(1, 10000):
        if i % 3 == 0:
            d += 'Fizz'
            f = True
        if i % 5 == 0:
            d += 'Buzz'
            f = True
        if f != True:
            print(i)
        else:
            print(d)
            d = ""
            f = False

Here they only check for i % 3 & i % 5 only once and add the string 'Fizz' & 'Buzz' to an empty string. And at the end, it just prints either the number or the final string.

This approach reduces the processing time, but it does increase memory consumption.

The final approach which is rare is...

def FizzBuzz():
    c3 = 0
    c5 = 0
    d = ""
    b = False
    for num in range(1, 10000):
        c3 += 1
        c5 += 1
        if c3 == 3:
            d += "fizz"
            c3 = 0
            b = True
        if c5 == 5:
            d += "buzz"
            c5 = 0
            b = True
        if b == True:
            print(d)
            d = ""
            b = False
        else:
            print(num)

Here in this approach, there are no (%) Modulo operators being used. hence it reduces the processing time of the code.

Testing

To test this theory I implemented the Pythons time function, and to my surprise. there was a drastic time difference between the first and the last code.

the timing results are as follows...

For 100 entries

1. First Version 0.0005862250000000027
2. Second Version 0.0002485049999999961
3. Third Version 0.001852885999999998

For 10000 entries

1. First Version 0.117162348
2. Second Version 0.188121156
3. Third Version 0.401831502

If you're stuck anywhere do leave a comment.
Follow me on Twitter at Twitter/pranjaljain0
Follow me on Github at github/pranjaljain0

Go to this gist for a complete code

Happy Hacking!

Comments

[Paddy3118]

The Modulo operator (%) is a heavy operator

There's your problem. It is quite fast in itself.

[Nathan Kallman]

Agreed, the problem isn't that it is slower (unless you're building a military grade FizzBuzz the difference is imperceptible). The actual problem (or I should say, the problem much more likely to be encountered) is when a change request comes in to add rules to "Woof on multiples of 7" the number of cases to check doubles (from 15, 5, 3 to 105, 35, 21, 15, 7, 5, 3)

[Pranjal Jain]

Yes true...
And when working in real-life applications...
we often encounter these sort of problems, where the correct algorithm wins.
just like Page rank over others...

[Paddy3118]

Solve today's problem. Fizzbuzz is Fizzbuzz.

[Pranjal Jain]

For 100 operations it might seem fast but for 10000 operations it starts to show a good difference.
here is the runtime of three functions with 10000 operations
6.550000000160594
2.3500000001508425
2.0000000000575113

[Paddy3118]

Unfortunately four numbers doesn't explain much.
Modulo is usually one machine code instruction. Other parts of the program will probably dwarf its execution time, such as I/O.