Start learning free

LESSON 181 OF 414 · LOOPS - CHALLENGES

Fizz Buzz in Scala: O(n) with a for Loop and Modulo

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 (i <- 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:
for (i <- 1 to n) {
	if (i % 15 == 0) {
		println("FizzBuzz")
	} else if (i % 3 == 0) {
		println("Fizz")
	} else if (i % 5 == 0) {
		println("Buzz")
	} else {
		println(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

    SCALA · LOOPS - CHALLENGES

    Fizz Buzz in Scala, explained

    Problem overview

    The method fizzBuzz(n: Int) prints the numbers from 1 to n, one per line, but replaces some of them with words. A multiple of 3 prints Fizz, a multiple of 5 prints Buzz, and a multiple of both prints FizzBuzz. Every other number prints as itself.

    For n = 15 the output starts 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14 and ends with FizzBuzz, because 15 is a multiple of both 3 and 5.

    Approach

    The method looks at each number once and decides what to print. The only difficulty is the order of the checks. A multiple of 15 is also a multiple of 3 and of 5, so if you test for 3 first, 15 would print Fizz and never reach the FizzBuzz case. Test the most specific condition first, then the others.

    A number is a multiple of both 3 and 5 exactly when it is a multiple of 15, so one test i % 15 == 0 handles that case.

    Here is how the chain treats a few values of i:

    iRemainders by 15, 3, 5First test that succeedsPrinted
    22, 2, 2none2
    99, 0, 4i % 3 == 0Fizz
    1010, 1, 0i % 5 == 0Buzz
    300, 0, 0i % 15 == 0FizzBuzz

    Because the chain stops at the first test that succeeds, 30 never reaches the Fizz or Buzz lines.

    How the remainder test works

    The expression i % 3 is the remainder after dividing i by 3. It is always 0, 1 or 2, and it is 0 exactly when i is a multiple of 3. For 9 the remainder is 0, for 10 it is 1, and for 11 it is 2. The same idea works for any divisor: i % 5 == 0 picks out 5, 10, 15 and so on. Both operands here are Int, so the result is an Int and compares directly with the literal 0.

    Notice that the pattern repeats every 15 numbers: 3 and 5 both divide 15, so the numbers 16 to 30 get words in exactly the same positions as 1 to 15: 18 is Fizz like 3, 20 is Buzz like 5, and 30 is FizzBuzz like 15. The loop does not rely on that repetition, but it explains why the single test for 15 is enough. Each test only looks at the current number, so the loop keeps no state between passes and the order of the lines is the order of the numbers.

    Step by step

    1. Loop from 1 to n inclusive with for (i <- 1 to n). The word to includes the upper bound.
    2. Check i % 15 == 0 first and print FizzBuzz. The remainder operator % gives 0 when i divides evenly.
    3. Then check i % 3 == 0 and print Fizz. Only numbers that are not multiples of 15 reach this line.
    4. Then check i % 5 == 0 and print Buzz.
    5. Otherwise print i itself. This is the final else.

    The solution in Scala

    class Solution {
    def fizzBuzz(n: Int): Unit = {
        for (i <- 1 to n) {
            if (i % 15 == 0) {
                println("FizzBuzz")
            } else if (i % 3 == 0) {
                println("Fizz")
            } else if (i % 5 == 0) {
                println("Buzz")
            } else {
                println(i)
            }
        }
    }
}

    Some Scala details:

    • 1 to n is a range. for (i <- 1 to n) runs for i equal to 1, 2, ..., n. 1 until n would stop at n - 1 and drop the last line. If n is 0, 1 to 0 is empty, so nothing is printed.
    • i is a val inside the loop. You cannot assign to it. Each pass gets a fresh value from the range.
    • println accepts any value. println("Fizz") prints a string and println(i) prints an Int, both followed by a line break. No conversion is needed.
    • Everything is an expression. The if/else if chain here is used for its side effects, and every branch has type Unit, so the loop body is a Unit too.
    • % keeps the sign of the dividend. This does not matter here, because i is always positive.

    An alternative: build the word

    The 15 test hard-codes the fact that 3 times 5 is 15. A version that grows if a third word is added builds the text from parts: start with an empty string, append Fizz when i % 3 == 0, append Buzz when i % 5 == 0, and print the number only if the string is still empty. For i = 15 both appends happen, which produces FizzBuzz without a separate case. This version prints the same output for n = 15. The lesson uses the chain of tests, which is the simpler form to read.

    Complexity

    Time: O(n). The loop runs exactly n times and each pass does at most three remainder tests and one print.

    Space: O(1). The only extra value is the loop variable i.

    Edge cases and common mistakes

    • Wrong order of checks. With the 3 test first, 15 prints Fizz instead of FizzBuzz. Another correct way is to test i % 3 == 0 && i % 5 == 0 first.
    • Using until. 1 until n never reaches n, so for n = 15 the final FizzBuzz line would be missing.
    • Printing a word and the number. Each number produces exactly one line. Use else, not a separate if that also prints i.
    • Spelling. The words are case-sensitive: fizzbuzz and Fizzbuzz do not match FizzBuzz.
    • n = 1. The loop prints a single line, 1.

    Testing

    • n = 1 prints 1.
    • n = 5 prints 1, 2, Fizz, 4, Buzz.
    • n = 15 ends with 14 and FizzBuzz.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free