Start learning free

LESSON 161 OF 347 · LOOPS - CHALLENGES

Fizz Buzz in C#: O(n) with a for Loop and the % 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

C# · LOOPS - CHALLENGES

Fizz Buzz in C#, explained

Problem overview

FizzBuzz(int n) prints the numbers from 1 to n, one per line, with three substitutions: multiples of 3 become Fizz, multiples of 5 become Buzz, and multiples of both become FizzBuzz.

For n = 15 the output is 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz. Notice that 15 is the first number divisible by both 3 and 5.

Approach

The statement asks for O(n) time and O(1) extra space. A single pass does that: visit each number once, decide what to print, and keep nothing except the loop counter.

The decision rests on divisibility, which the remainder operator % tests. i % 3 == 0 means 3 divides i exactly. The only subtlety is that a multiple of 15 satisfies both the "3" and the "5" tests, so the order of the checks matters.

Step by step

Loop from 1 to n inclusive. A for loop with int i = 1 and the condition i <= n visits exactly the numbers the task names. Starting at 0 would print FizzBuzz first, because 0 is divisible by everything.
Check 15 first. A number divisible by both 3 and 5 is divisible by 15, and it must print FizzBuzz. If you tested 3 first, 15 would print Fizz and never reach the other branches.
Then check 3, then 5. Chained else if branches make sure exactly one thing is printed per number.
Otherwise print the number. The final else covers every number with no special rule.

The solution in C#

class Solution {
    public void FizzBuzz(int n) {
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) {
                Console.WriteLine("FizzBuzz");
            } else if (i % 3 == 0) {
                Console.WriteLine("Fizz");
            } else if (i % 5 == 0) {
                Console.WriteLine("Buzz");
            } else {
                Console.WriteLine(i);
            }
        }
    }
}

Some C# details:

Console.WriteLine has overloads for both text and numbers. Passing a string prints the text; passing the int i prints its digits. Each call ends with a line break.
String literals use double quotes. The text "Fizz" must be spelled and capitalized exactly as the task shows it.
The conditions need parentheses. C# requires them around each if condition, and else if is written as two words.

Tracing a few values

Running the chain by hand on a few numbers shows why the order works:

i = 7: 7 % 15, 7 % 3 and 7 % 5 are 7, 1 and 2, none of them 0, so the else prints 7.
i = 9: 9 % 15 is 9, but 9 % 3 is 0, so it prints Fizz.
i = 10: 10 % 15 is 10 and 10 % 3 is 1, but 10 % 5 is 0, so it prints Buzz.
i = 30: 30 % 15 is 0, so it prints FizzBuzz and skips the rest of the chain.

Why 15 and not "3 and 5"

The numbers 3 and 5 share no factor other than 1, so a number is divisible by both exactly when it is divisible by their product, 15. Testing i % 15 == 0 is a shorter way to write i % 3 == 0 && i % 5 == 0. Both are correct, and the second makes the "both" idea more obvious, so use whichever reads better to you.

Another way to avoid the special case is to build the text piece by piece. Start with an empty string, append "Fizz" when 3 divides i, append "Buzz" when 5 divides i, and print the number only if the string is still empty. It produces the same output, but it uses a string variable per iteration, so it is slightly more work than the plain chain. The chain is the clearer choice for this lesson.

Complexity

Time: O(n). The loop runs exactly n times, and each iteration does a constant number of remainder tests and one print.

Space: O(1). The only variable is i. Nothing is collected into a list or a string, because every line is printed as soon as it is decided.

Edge cases and common mistakes

Wrong branch order. Putting the % 3 test before the % 15 test means multiples of 15 print Fizz. The usual alternative is to test % 3 == 0 && i % 5 == 0 first, which gives the same result as % 15.
Separate if statements instead of else if. Without the chain, 15 would match several conditions and print more than once.
Off-by-one on the range. i < n stops one number early, and the last line of the expected output goes missing.
Small n. For n = 1 the output is just 1. For n = 3 it is 1, 2, Fizz.
Using = instead of ==. i % 3 = 0 doesn't compile in C#. The comparison operator is ==.

Variations worth knowing

The same structure handles any set of rules. If the task added "multiples of 7 print Bang", you would need a check for every combination in the chain, which grows quickly, and the build-the-text approach becomes the better fit. For this lesson two rules are enough, and the plain chain is easy to read and easy to get right.

Testing

n = 15 gives the 15 lines listed above, ending in FizzBuzz.
n = 5 gives 1, 2, Fizz, 4, Buzz.
n = 1 gives 1.

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

Start learning free