Start learning free

LESSON 162 OF 348 · LOOPS - CHALLENGES

Fizz Buzz in TypeScript: O(n) Loop with the Modulo Operator

Practice O(n) Homework 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 : 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:

SOLVE IT YOURSELF
Ctrl + Enter to check

TYPESCRIPT · LOOPS - CHALLENGES

Fizz Buzz in TypeScript, explained

Problem overview

The method fizzBuzz(n) prints the numbers from 1 to n, one per line, with three substitutions. A multiple of 3 prints Fizz instead of the number. A multiple of 5 prints Buzz. A multiple of both 3 and 5 prints FizzBuzz. For n = 15 the output starts 1, 2, Fizz, 4, Buzz, and ends with 13, 14, FizzBuzz. The method prints and returns nothing.

The statement asks for O(n) time and O(1) extra space. A single pass over the numbers does that.

Approach: one loop, one decision per number

Loop over i from 1 to n. For each value, decide which of four outputs applies: FizzBuzz, Fizz, Buzz or the number itself. The test for "multiple of k" is i % k === 0: the remainder operator % gives what is left after dividing, so a remainder of 0 means i divides evenly by k.

The order of the checks is the key point. A number such as 15 is a multiple of 3 and also of 5, so it satisfies the "Fizz" test and the "Buzz" test. If you test 3 first, you print Fizz and never reach the case you needed. The combined case must come first. A number is a multiple of both 3 and 5 exactly when it is a multiple of 15, so a single check i % 15 === 0 handles it.

Printing is also the only output: the method has no return value, so nothing is collected in an array. That is why the extra space stays constant however large n is.

Step by step

  1. Write a for loop with let i = 1 that continues while i <= n. It starts at 1, not 0, and includes n.
  2. Check i % 15 === 0 first and print "FizzBuzz".
  3. Chain an else if for 3 and print "Fizz".
  4. Chain another else if for 5 and print "Buzz".
  5. Finish with else and print the number i.

Because the branches are chained with else if, at most one of them runs for each number.

The solution in TypeScript

class Solution {
    fizzBuzz(n: number): void {
        for (let i = 1; i <= n; i++) {
            if (i % 15 === 0) {
                console.log("FizzBuzz");
            } else if (i % 3 === 0) {
                console.log("Fizz");
            } else if (i % 5 === 0) {
                console.log("Buzz");
            } else {
                console.log(i);
            }
        }
    }
}

Two details are worth knowing. First, the comparisons use ===, the strict equality operator, which never converts types. It is the habit to keep in TypeScript, since == can convert values in surprising ways. Second, console.log(i) prints a number and console.log("Fizz") prints a string, but both appear as plain text on a line, with no quotes. The parameter n has type number, and TypeScript has no separate integer type, so the type doesn't stop a caller from passing 2.5; the lesson promises a positive integer.

How the remainder works

The expression 7 % 3 is 1, because 7 is two threes and one left over. 15 % 5 is 0, because 5 goes into 15 exactly, and 4 % 5 is 4, because 5 doesn't fit into 4 at all. Only a remainder of 0 means "multiple". Operator precedence puts % before ===, so i % 15 === 0 needs no extra parentheses.

Another way to organise the checks

If the multiple-of-15 shortcut feels like a trick, you can build the word from its parts and print the number only when no part was added:

function fizzBuzz2(n: number): void {
  for (let i = 1; i <= n; i++) {
    let word = "";
    if (i % 3 === 0) word += "Fizz";
    if (i % 5 === 0) word += "Buzz";
    console.log(word === "" ? i : word);
  }
}

For 15 both conditions hold, so word becomes "FizzBuzz" by itself, and the order of the checks no longer matters. The output for n = 15 is the same as the lesson's. This version also extends well: adding a rule for 7 is one more line. The lesson's version is shorter to read for exactly two rules.

Complexity

The loop runs exactly n times and each iteration does a fixed number of remainder checks and one print, so the time is O(n). The only extra variable is the loop index i, so the extra space is O(1).

Edge cases and common mistakes

  • Testing 3 or 5 before 15. The output for 15 becomes Fizz, and so does every other multiple of 15. This is the classic mistake.
  • Using two independent ifs without else. Then 15 would print Fizz and also Buzz on separate lines. If you want separate checks, build a string instead and print the number only when the string is empty.
  • Off-by-one loop bounds. Starting at 0 would print FizzBuzz first, because 0 is a multiple of everything. Stopping at i < n would drop n.
  • An input of 0 or less. The loop condition 1 <= n is false at once, so nothing is printed. The lesson promises a positive n, but it is good to know what the loop does without that promise.
  • Using = instead of === in a condition. That assigns instead of comparing.

Testing

With n = 5 the output is 1, 2, Fizz, 4, Buzz. With n = 1 it is just 1. With n = 15 the last line is FizzBuzz, the only line that needs the combined case.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free