## Thursday, April 3, 2014

### Fizz Buzz

Problem
Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz"
Example of sequence - 3,6,9,12,15,18,1,24,27.

Solution
Method 1- Brute force
Here we notice that that after 15, there is 18. So, we should increment the iterator by 2, and then 1 i.e. 3. This will avoid some of the division step.
```public static void main(String args[]) {
StringBuilder sb = new StringBuilder(700);
for (int k = 1; k <= 100; ) {
if (k % 15 == 0) {
sb.append("FizzBuzz\n");
k+=2;//optimization
} else if (k % 3 == 0) {
sb.append("Fizz\n");
} else if (k % 5 == 0) {
sb.append("Buzz\n");
} else {
sb.append(k);
sb.append("\n");
}
k++;
}
System.out.println(sb.toString());
}
```

Method 2 - Generate the multiplication table
This method is inspired by sieve of Eratosthenes. Here we can get 2 sequence of 3 and 5. If the numbers are equal we print FizzBuzz, otherwise print fizz buzz acordingly. So, rather than going throuh loop, we can have 2 sequences and avoid numbers like 7,8 which are neither multiple of 3 or 5.

We need a sequence which could give us multiple of a number :
```interface Sequence {
int peek();
int next();
}
class MultipleSequence implements Sequence{
private int multiple;
private final int seed;

MultipleSequence(final int seed) {
this.seed = seed;
}

@Override
public int peek(){
return multiple + seed;
}

@Override
public int next(){
return multiple += seed;
}
}
```

Now lets implement the iterator and iterable interface in java
```class MultipleIterator implements Iterator<Integer> {

private final Sequence mult3 = new MultipleSequence(3);
private final Sequence mult5 = new MultipleSequence(5);
private final int limit;
private int multiple;

MultipleIterator(int limit){
this.limit = limit;
}

@Override
public Integer next(){
if(mult3.peek() < mult5.peek()){
multiple = mult3.next();
System.out.println("Fizz");
}else if(mult3.peek() > mult5.peek()){
multiple = mult5.next();
System.out.println("Buzz");
}else {//if they are equal
multiple = Math.max(mult3.next(), mult5.next());
System.out.println("FizzBuzz");
}
return multiple;
}

@Override
public boolean hasNext(){
return multiple < limit;
}

@Override
public void remove(){
throw new UnsupportedOperationException();
}
}
```

Finally, I could simply provide a public class to iterate over the given sequence by implementing the Iterable interface.
```public static class Sequencer implements Iterable<Integer> {
private final int limit;
public Sequencer(int limit){
this.limit = limit;
}

public Iterator<Integer> iterator(){
return new MultipleIterator(limit);
}
}
```

The main method
```public static void main(String args[]){

for(int val: new Sequencer(100)){

}

}
```

Thanks

References
http://stackoverflow.com/questions/10466709/fizzbuzz-print-string-depending-on-number