Start learning free

LESSON 184 OF 414 · LOOPS - CHALLENGES

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

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

Guided

Ctrl + Enter to check

RUST · LOOPS - CHALLENGES

Fizz Buzz in Rust, explained

Problem overview

The function fizz_buzz takes a positive integer n and prints the numbers from 1 to n, one per line, with these replacements:

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 is 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz. Position 15 is the first number divisible by both 3 and 5, so it is the first FizzBuzz.

The statement asks for O(n) time and O(1) extra space. Nothing needs to be stored, since each line depends only on the current number, so the problem fits those limits naturally.

Approach

Go through the numbers from 1 to n once and decide for each what to print. The decision is a chain of conditions, and the order of the chain is the interesting part. A number divisible by 15 is divisible by 3 and by 5, so if the checks for 3 or 5 came first, they would catch it and print only Fizz or Buzz. The both-case has to be tested first.

Testing divisibility by 15 works because 3 and 5 share no factors: a number is a multiple of both exactly when it is a multiple of their product. The alternative is to test i % 3 == 0 && i % 5 == 0 first, which gives the same results.

Step by step

Loop from 1 to n inclusive. The range 1..=n includes its end. The range 1..n would stop at n - 1 and skip the last line.
Check 15 first. If i % 15 == 0, print FizzBuzz.
Then check 3. Reaching this branch means the number is not a multiple of 15, so a multiple of 3 here is a plain Fizz.
Then check 5. In the same way, a multiple of 5 that got here is a plain Buzz.
Otherwise print the number itself with println!("{}", i).

Each branch of the if ... else if chain runs only when all the earlier conditions were false. That is what makes the order work.

The solution in Rust

impl Solution {
    fn fizz_buzz(n: i32) {
        for i in 1..=n {
            if i % 15 == 0 {
                println!("FizzBuzz");
            } else if i % 3 == 0 {
                println!("Fizz");
            } else if i % 5 == 0 {
                println!("Buzz");
            } else {
                println!("{}", i);
            }
        }
    }
}

Language details:

1..=n is an inclusive range, and for in Rust always iterates over something iterable. There is no C-style for (i = 1; i <= n; i++). The loop variable i has the type of n, which is i32, and it needs no mut.
Conditions in if have no parentheses, and they must be a bool: if i % 15 alone would not compile. The braces are required.
println!("Fizz") prints a string literal and a newline. For the number, the placeholder {} formats i, as in println!("{}", i).
% is the remainder operator. For the positive values here it behaves as you expect: 7 % 3 is 1. For negative numbers the result takes the sign of the left side, but this loop never has any.
Each branch ends in a println! statement with a semicolon, so the whole chain evaluates to (), and the function returns nothing.

Another way to see it

The words can also be built piece by piece: start with an empty text, add Fizz when the number is a multiple of 3, add Buzz when it is a multiple of 5, and print the number only if the text is still empty. That version never mentions 15, which is convenient when a rule such as Bazz for 7 is added later, because each new rule is one more independent check instead of a new combination of conditions. The chain in the lesson is simpler for exactly two rules.

Complexity

The loop runs exactly n times and each iteration does a constant amount of work: a few remainder operations and one print. The time is O(n). The only variable is the loop counter, so the extra space is O(1). Printing the output itself is not counted as memory the algorithm keeps.

Edge cases and common mistakes

Checking 3 or 5 before 15. The number 15 would print Fizz and the FizzBuzz branch could never run.
Using 1..n. The last number is missing. For n = 15 the final line would be 14.
Starting at 0. Zero is divisible by 3 and 5, so a loop from 0 would print FizzBuzz first.
n = 1. The loop runs once and prints 1.
Two separate if statements for 3 and for 5, without else: a multiple of 3 would print both its word and then the number, unless each branch guards the other. Use one chain.
n = 0 or negative. The range 1..=n is empty, so nothing is printed and the function simply returns. The problem promises a positive n, so this is only a matter of knowing the behaviour.

Testing

n = 1 prints 1.
n = 5 prints 1, 2, Fizz, 4, Buzz.
n = 15 ends with FizzBuzz, and n = 30 ends with a second FizzBuzz.

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

Start learning free