Fizz Buzz in C++ 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 in teaching basic control flow and modulus operations, which are fundamental in programming. Common applications include interview questions and coding practice for beginners.

Approach

To solve this problem, we need to iterate through numbers from 1 to n and check each number for divisibility by 3, 5, and both. A naive solution would involve checking each condition separately, but this can be optimized by checking for the most specific condition (divisibility by both 3 and 5) first.

Naive Solution

The naive solution involves checking each number for divisibility by 3, 5, and both using if-else statements. This approach is straightforward but not the most efficient in terms of readability and maintainability.

Optimized Solution

The optimized solution involves checking for divisibility by 15 first (since 15 is the least common multiple of 3 and 5), followed by checks for 3 and 5. This ensures that the most specific condition is checked first, reducing the number of checks needed.

Algorithm

The algorithm can be broken down into the following steps:

Iterate through numbers from 1 to n.
For each number, check if it is divisible by 15. If true, print "FizzBuzz".
If not divisible by 15, check if it is divisible by 3. If true, print "Fizz".
If 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

#include <iostream>
using namespace std;

void fizzBuzz(int n) {
    for (int i = 1; i <= n; ++i) {
        // Check if the number is divisible by both 3 and 5
        if (i % 15 == 0) {
            cout << "FizzBuzz" << endl;
        }
        // Check if the number is divisible by 3
        else if (i % 3 == 0) {
            cout << "Fizz" << endl;
        }
        // Check if the number is divisible by 5
        else if (i % 5 == 0) {
            cout << "Buzz" << endl;
        }
        // If none of the above, print the number itself
        else {
            cout << i << endl;
        }
    }
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;
    fizzBuzz(n);
    return 0;
}

Complexity Analysis

The time complexity of this solution is O(n) because we iterate through the numbers from 1 to n exactly once. The space complexity is O(1) as 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 = 0: No output should be produced as the range is empty.
n = 15: The output should include "FizzBuzz" at the 15th position.

These edge cases can be tested by running the function with different values of n and verifying the output.

Testing

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

n = 1: Expected output is "1".
n = 3: Expected output is "1, 2, Fizz".
n = 5: Expected output is "1, 2, Fizz, 4, Buzz".
n = 15: Expected output is "1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz".

These test cases cover simple, intermediate, and edge cases to ensure the solution works correctly.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Think about the most specific conditions first to optimize your checks.
Write pseudo-code to outline your approach before implementing it in code.
Test your solution with a variety of test cases, including edge cases.

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

Conclusion

In this blog post, we discussed the Fizz Buzz problem, its significance, and how to approach solving it. We provided a detailed algorithm, code implementation in C++, and complexity analysis. Understanding and solving such problems is crucial for developing strong programming skills. We encourage readers to practice and explore further.

Additional Resources

For further reading and practice problems, consider the following resources: