Fizz Buzz in Java with O(n) Time Complexity

Given a positive integer n print each number from 1 to n, each on a new line.
For each multiple of 3, print "Fizz" instead of the number.
For each multiple of 5, print "Buzz" instead of the number.
For numbers which are multiples of both 3 and 5, print "FizzBuzz" instead of the number.

Example:

Input: n = 15
Output:
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

Note:

Your algorithm should run in O(n) time and use O(1) space.

Understanding the Problem

The core challenge of the Fizz Buzz problem is to correctly identify and print the appropriate string or number based on the divisibility rules. This problem is significant as it is often used in coding interviews to test a candidate's understanding of loops, conditionals, and basic algorithmic thinking.

Approach

To solve this problem, we need to iterate through the numbers from 1 to n and apply the following rules:

If the number is divisible by both 3 and 5, print "FizzBuzz".
If the number is divisible by 3, print "Fizz".
If the number is divisible by 5, print "Buzz".
If none of the above conditions are met, print the number itself.

We can achieve this using a simple for loop and conditional statements.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize a for loop to iterate from 1 to n.
For each iteration, check if the current number is divisible by both 3 and 5 using the modulo operator (%).
If true, print "FizzBuzz".
If not, check if the number is divisible by 3. If true, print "Fizz".
If not, check if the number is divisible by 5. If true, print "Buzz".
If none of the above conditions are met, print the number itself.

Code Implementation

public class FizzBuzz {
    public static void main(String[] args) {
        int n = 15; // Example input
        for (int i = 1; i <= n; i++) {
            // Check if the number is divisible by both 3 and 5
            if (i % 15 == 0) {
                System.out.println("FizzBuzz");
            } 
            // Check if the number is divisible by 3
            else if (i % 3 == 0) {
                System.out.println("Fizz");
            } 
            // Check if the number is divisible by 5
            else if (i % 5 == 0) {
                System.out.println("Buzz");
            } 
            // If none of the above, print the number itself
            else {
                System.out.println(i);
            }
        }
    }
}

Complexity Analysis

The time complexity of this algorithm is O(n) because we are iterating through the numbers from 1 to n exactly once. The space complexity is O(1) as we are not using any additional space that grows with the input size.

Edge Cases

Some potential edge cases include:

n = 1: The output should be "1".
n = 0: There should be no output as the range is empty.
n = 3: The output should be "1, 2, Fizz".

These edge cases can be tested to ensure the algorithm handles them correctly.

Testing

To test the solution comprehensively, consider the following test cases:

n = 1: Output should be "1".
n = 5: Output should be "1, 2, Fizz, 4, Buzz".
n = 15: Output should be "1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz".

Using a testing framework like JUnit can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching problems like Fizz Buzz, consider the following tips:

Break down the problem into smaller, manageable parts.
Use pseudo-code to outline your approach before writing actual code.
Test your solution with different inputs to ensure it handles all edge cases.

Practicing similar problems and studying algorithms can help improve problem-solving skills.

Conclusion

In this blog post, we discussed the Fizz Buzz problem, its significance, and how to solve it using a simple algorithm in Java. We also covered complexity analysis, edge cases, and testing strategies. Understanding and solving such problems is crucial for developing strong algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: