Start learning free

LESSON 177 OF 410 · LOOPS - CHALLENGES

Fizz Buzz in JavaScript with O(n) Time Complexity

Practice O(n) Read the full explanation

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 from 1 to 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, which gives the remainder of a division (i % 15 == 0 means that i is divisible by 15):
for each i from 1 to n:
	if i is divisible by 15, print "FizzBuzz"
	otherwise, if i is divisible by 3, print "Fizz"
	otherwise, if i is divisible by 5, print "Buzz"
	otherwise, 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:

STEP 1 OF 5
    Ctrl + Enter to check

    JAVASCRIPT · LOOPS - CHALLENGES

    Fizz Buzz in JavaScript, explained

    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 educational tools for teaching programming and logic, as well as simple game mechanics.

    Potential pitfalls include not correctly handling the order of conditions, which can lead to incorrect outputs.

    Approach

    To solve this problem, we need to iterate through 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.

    A naive solution would involve checking each condition separately, but this can be optimized by checking the most specific condition (divisibility by both 3 and 5) first.

    Algorithm

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

    1. Initialize a loop that runs from 1 to n.
    2. For each number, check if it is divisible by both 3 and 5 (i.e., i % 15 == 0).
    3. If true, print "FizzBuzz".
    4. Otherwise, check if it is divisible by 3 (i.e., i % 3 == 0).
    5. If true, print "Fizz".
    6. Otherwise, check if it is divisible by 5 (i.e., i % 5 == 0).
    7. If true, print "Buzz".
    8. If none of the above conditions are met, print the number itself.

    Code Implementation

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

    Complexity Analysis

    The time complexity of this algorithm 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.
    • n = 15: The output should include "FizzBuzz" at the 15th position.

    To test these edge cases, we can run the algorithm with different values of n and verify the outputs.

    Testing

    To comprehensively test the solution, we should include a variety of test cases:

    • Simple cases: n = 1, n = 2
    • Typical cases: n = 15, n = 30
    • Edge cases: n = 0, n = 100

    We can use JavaScript's console.log to print the outputs and manually verify them.

    Thinking and Problem-Solving Tips

    When approaching such problems, it is essential to:

    • Understand the problem requirements and constraints.
    • Break down the problem into smaller, manageable parts.
    • Consider edge cases and how to handle them.
    • Write clean, readable code with comments explaining the logic.

    To improve problem-solving skills, practice solving similar problems and study different algorithms and their applications.

    Conclusion

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

    Additional Resources

    For further reading and practice, consider the following resources:

    • LeetCode - A platform for practicing coding problems.
    • HackerRank - JavaScript tutorials and challenges.
    • MDN Web Docs - Comprehensive JavaScript documentation and guides.
    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free