Wednesday, February 18, 2015

The Fizz Buzz Problem

There is a rather fun, tricky, and common challenge in the Computer Science world. Whether you are a software engineer or an intern code-monkey, this will come up in your interview at some point. "Fizz Buzz" really is a children's math challenge, reviewing their division skills. It has been implemented as a coding challenge and as a common way for programmers to prove their worth. The problem goes like this:

Write a program that prints the integers from 1 to 100. But for the multiples of three print "Fizz" instead of the number, and for the multiples of five print "Buzz" instead of the number. For numbers which are multiples of both three and five, print "FizzBuzz" instead of the number.
Seems easy enough, right? Until you get to coding it. Many people approach this problem confidently, only to find out that their methods (lol) do not seem to work. Let's work through it, so that you aren't embarrassed when your CS instructor puts it on a quiz. As with every computer science problem, I will think about what I expect to get from this code first. (If you haven't seen my post on this, click here). Here are my test cases for what this program requires of us:

Test Cases
if the number is... output should be...
1 1
3 Fizz
5 Buzz
15 FizzBuzz
... ...

Okay, this seems straightforward. Are there any border cases or special numbers or inputs that we have to think about? If we were to categorize the numbers between 1 and 100 in reference to our expected outputs, it would probably look like:
  • Numbers divisible by 3
  • Numbers divisible by 5
  • Numbers divisible by 3 and 5
  • Numbers not divisible by 3 or 5
Let's think about it a step further. Since our range is only 1 to 100, there is at maximum 100 things we need to worry about. Interestingly, we can hard-code this problem and get the exact result that we want. Although time consuming and literally not the point of a program, it can be done. This would not, however, land you a job. We want to let the computer make decisions for an algorithm with conditions, just in case I go insane and ask for the same output for the range 1 to 10,000. Let's think about our times tables.


In this table, any number in yellow is a multiple of 3 only, any number in blue is a multiple of 5 only, and any number in green is a multiple of both 3 and 5. You can see that the green ones are at the same time multiples of 15. Any other number is in a clear square. What does this tell us about our program? Any number that has any type of color is going to be one of the three words. All the others are just going to be the plain numbers. So we've gone from needing to worry about 100 outputs to just 47. Now, you can still take this information and just hard-code like a noob, but we're going to think about it further. How can we translate this knowledge into something like psuedocode?

The modulus operator comes in handy when checking for factors. This program will probably utilize that in the heart of its calculations. Also, order does matter (as it does in a lot of cases, unless you're sorting...) Let's see what we can come up with.

1    for i in range (1, 101):
2        if ((i % 3 == 0) and (i % 5 == 0)):
3            print "FizzBuzz"
4        if (i % 3 == 0):
5            print "Fizz"
6        elif (i % 5 == 0):
7            print "Buzz"
8        else:
9            print i
This looks promising. We're essentially saying, line-by-line, that:
  1.  As long as i is within 1 and 101, increasing by one...
  2.  First, check if i divides by 3 evenly and 5 evenly,
  3. If so, print the word "FizzBuzz"
  4. Now check if i divides by 3 evenly,
  5. If so, print the word "Fizz"
  6. If the above test fails, check that i divides by 5 evenly,
  7. If so, print the word "Buzz",
  8. Otherwise, if everything above failed,
  9. Just print i
This will work because the order is correct and our decision statements are nested properly. Now, it's time to put this in the syntax of the language you are using. 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def FizzBuzz():
 for i in range (1, 101):
  if (i % 3 == 0 and i % 5 == 0):
   print "FizzBuzz"
  if (i % 3 == 0):
   print "Fizz"
  elif (i % 5 == 0):
   print "Buzz"
  else:
   print i
FizzBuzz()




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class FizzBuzz {

    public static void main(String[] args) {
        
        fizzBuzz(1,100);
    }
    public static void fizzBuzz(int lower, int upper) {
            
            for (int i = lower; i <= upper; i++) {
                String currentNum = "";
                currentNum += (i % 3) == 0 ? "Fizz" : "";
                currentNum += (i % 5) == 0 ? "Buzz" : "";
                System.out.println(!currentNum.isEmpty() ? currentNum : i);
            }

    }
}
Posted by