Start learning free

LESSON 162 OF 338 · LOOPS - CHALLENGES

Fizz Buzz in Go: O(n) Time and O(1) Space

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

GO · LOOPS - CHALLENGES

Fizz Buzz in Go, explained

Problem overview

The function fizzBuzz receives a positive integer n and 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 instead;
a multiple of both 3 and 5 prints FizzBuzz.

For n = 15 the output begins 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14 and ends with FizzBuzz, since 15 is the first number divisible by both. The function prints and returns nothing. The task asks for O(n) time and O(1) extra space.

Approach: one pass with ordered checks

Every number from 1 to n needs exactly one decision, so a single loop is enough. That is already O(n), and printing as you go means nothing needs to be stored, which gives O(1) extra space.

The only real question is the order of the checks. A number like 15 is a multiple of 3 and also a multiple of 5. If the loop tested "multiple of 3" first, it would print Fizz and never reach the FizzBuzz case. So the most specific condition goes first. A number is a multiple of both 3 and 5 exactly when it is a multiple of 15, because 3 and 5 share no factor. One test, i % 15 == 0, covers that case.

The remainder operator % gives what is left after division. A number is a multiple of k exactly when i % k == 0.

Step by step

Loop from 1 to n. Use a for loop with i starting at 1 and a condition of i <= n, so that n itself is included.
Test for 15 first. If i % 15 == 0, print FizzBuzz.
Then test for 3. Reaching this branch means i is not a multiple of 15, so a multiple of 3 here prints Fizz.
Then test for 5 and print Buzz in the same way.
Otherwise print the number. The final else handles everything left over.

The solution in Go

func fizzBuzz(n int) {
    for i := 1; i <= n; i++ {
        if i % 15 == 0 {
            fmt.Println("FizzBuzz")
        } else if i % 3 == 0 {
            fmt.Println("Fizz")
        } else if i % 5 == 0 {
            fmt.Println("Buzz")
        } else {
            fmt.Println(i)
        }
    }
}

Go details worth knowing:

No parentheses, required braces. The conditions of if and for aren't wrapped in parentheses, and the braces are always required. else if goes on the same line as the closing brace of the previous block: } else if ... {. Putting else on a new line is a syntax error.
fmt.Println accepts any type. It prints the string "Fizz" as text and the integer i as a number, adding a newline either way. No conversion to string is needed. The fmt package has to be imported in a complete program.
Spacing in expressions. The solution writes i % 15 == 0 with spaces. The Go formatter, gofmt, would write i%15 == 0 in this position, but the two forms mean the same.
No truthiness. Go requires the condition to be a real bool. if i % 3 { doesn't compile, so the comparison with 0 is required.
Loop variable. i := 1 in the for header is visible only inside the loop.

Other ways to write it in Go

Go has no ternary operator, but it has a switch with no expression, which reads like an if chain. Each case holds a condition, the first true case runs, and Go does not fall through to the next one, so no break is needed:

func fizzBuzz(n int) {
    for i := 1; i <= n; i++ {
        switch {
        case i%15 == 0:
            fmt.Println("FizzBuzz")
        case i%3 == 0:
            fmt.Println("Fizz")
        case i%5 == 0:
            fmt.Println("Buzz")
        default:
            fmt.Println(i)
        }
    }
}

It prints the same lines. The order of the cases matters here for the same reason as before: the combined case comes first.

A second variant avoids the 15 test. Build the word for each number: add Fizz when i % 3 == 0, add Buzz when i % 5 == 0, and print the number only if the word is still empty. That scales better if more rules are added, such as a word for 7, because each rule is one independent check. For three rules the plain chain is simpler, so the lesson uses it.

Complexity

Time: O(n). The loop runs exactly n times, and each pass does at most three remainder checks and one print, which is constant work.

Space: O(1). The only variable is the loop counter i. The function builds no slice and no string, because each line is printed as soon as it is decided.

Edge cases and common mistakes

Checking 3 before 15. The most common mistake. For 15 the program would print Fizz and skip the FizzBuzz branch. The combined case always comes first.
Dropping the else keywords. If each test is its own if, the branches are no longer exclusive. With the checks for 3 and 5 as separate if statements and a final else attached only to the last one, a multiple of 3 prints Fizz and then the number too. The else if chain guarantees exactly one line per number.
Stopping at n - 1. With i < n the last number is never printed. The loop needs <=.
Starting at 0. Since 0 % 15 == 0, a loop starting at 0 would print an extra FizzBuzz as the first line.
Small values of n. For n = 1 the output is just 1. For n = 3 it is 1, 2, Fizz.

Testing

n = 1 prints 1.
n = 5 prints 1, 2, Fizz, 4, Buzz.
n = 15 ends with 14 and then FizzBuzz.
n = 16 adds 16 after FizzBuzz.

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

Start learning free