Fizz Buzz in Python 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.

Hints:

In order to print the items, we should iterate through the numbers 1 to n and check for each of them what condition is satisfied to print accordingly. How can we do this?

Let's use a for loop and a variable i to iterate through the numbers 1 to n:

for each i : 1 -> n:
	# Print either i or "Fizz" or "Buzz" or "FizzBuzz"

Inside the loop, we need to decide what should be printed between Fizz, Buzz, FizzBuzz and i.
How can we do this?

Using sequential if - else statements along with the modulo (%) operator:

for each i : 1 -> n:
	if i % 15 == 0:
    		print("FizzBuzz")
  	else if i % 3 == 0:
    		print("Fizz")
  	else if i % 5 == 0:
    		print("Buzz")
  	else:
    		print(i)

We have a for loop that performs exactly n iterations, thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).

Video Solution:

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 in many coding interviews as it tests basic programming skills, including loops, conditionals, and modulo operations. Common applications include simple game development and educational tools for teaching programming concepts.

Potential pitfalls include forgetting to check for multiples of both 3 and 5 first, which can lead to incorrect outputs. Misunderstanding the problem requirements or incorrectly implementing the modulo operation can also cause issues.

Approach

To solve the Fizz Buzz problem, we can start with a naive solution and then optimize it. The naive solution involves iterating through each number from 1 to n and using a series of if-else statements to determine what to print.

However, this naive solution is already optimal in terms of time complexity (O(n)) and space complexity (O(1)). Therefore, we will focus on explaining the thought process and ensuring the solution is clear and correct.

Naive Solution

The naive solution involves iterating through each number from 1 to n and using if-else statements to check the divisibility conditions:

for i in range(1, n + 1):
    if i % 15 == 0:
        print("FizzBuzz")
    elif i % 3 == 0:
        print("Fizz")
    elif i % 5 == 0:
        print("Buzz")
    else:
        print(i)

This solution is straightforward and meets the problem's requirements.

Algorithm

Let's break down the algorithm step-by-step:

Initialize a loop that iterates from 1 to n (inclusive).
For each iteration, check if the current number is divisible by 15 (both 3 and 5). If true, print "FizzBuzz".
If the number is not divisible by 15, check if it is divisible by 3. If true, print "Fizz".
If the number is not divisible by 3, check if it is divisible by 5. If true, print "Buzz".
If none of the above conditions are met, print the number itself.

Code Implementation

Here is the Python code implementation for the Fizz Buzz problem:

def fizz_buzz(n):
    # Iterate from 1 to n
    for i in range(1, n + 1):
        # Check if the number is divisible by both 3 and 5
        if i % 15 == 0:
            print("FizzBuzz")
        # Check if the number is divisible by 3
        elif i % 3 == 0:
            print("Fizz")
        # Check if the number is divisible by 5
        elif i % 5 == 0:
            print("Buzz")
        # If none of the above, print the number itself
        else:
            print(i)

# Example usage
fizz_buzz(15)

Complexity Analysis

The time complexity of this solution is O(n) because we iterate through each number from 1 to n exactly once. The space complexity is O(1) because we only use a constant amount of extra space for the loop variable.

Edge Cases

Potential edge cases include:

n = 1: The output should be "1".
n = 3: The output should be "1, 2, Fizz".
n = 5: The output should be "1, 2, Fizz, 4, Buzz".
n = 0: The function should handle this gracefully, possibly by not printing anything.

To test these edge cases, we can call the function with different values of n and verify the output.

Testing

To test the solution comprehensively, we can use a variety of test cases:

def test_fizz_buzz():
    import io
    import sys

    # Capture the output
    captured_output = io.StringIO()
    sys.stdout = captured_output

    # Test case 1
    fizz_buzz(1)
    assert captured_output.getvalue().strip() == "1"

    # Test case 2
    captured_output.truncate(0)
    captured_output.seek(0)
    fizz_buzz(3)
    assert captured_output.getvalue().strip() == "1\n2\nFizz"

    # Test case 3
    captured_output.truncate(0)
    captured_output.seek(0)
    fizz_buzz(5)
    assert captured_output.getvalue().strip() == "1\n2\nFizz\n4\nBuzz"

    # Test case 4
    captured_output.truncate(0)
    captured_output.seek(0)
    fizz_buzz(15)
    assert captured_output.getvalue().strip() == "1\n2\nFizz\n4\nBuzz\nFizz\n7\n8\nFizz\nBuzz\n11\nFizz\n13\n14\nFizzBuzz"

    # Reset redirect.
    sys.stdout = sys.__stdout__

    print("All tests passed.")

# Run tests
test_fizz_buzz()

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 a variety of test cases, including edge cases.
Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed the Fizz Buzz problem, its significance, and how to solve it using a simple and efficient algorithm. We provided a detailed explanation of the approach, code implementation, complexity analysis, and testing. Understanding and solving such problems is crucial for developing strong programming skills.

We encourage you to practice and explore further to enhance your problem-solving abilities.

Additional Resources

For further reading and practice problems related to Fizz Buzz, consider the following resources: