Problem overview
The method PrintMultiples(int A, int B) prints, one per line, the first A positive numbers that are divisible by B. It returns nothing; the result is what appears on the console. A number X is divisible by B when X % B == 0, that is, when dividing leaves no remainder.
For A = 5 and B = 3 the output is 3, 6, 9, 12 and 15. These are the first five numbers whose remainder modulo 3 is 0. The number 0 also has that property, but the lesson's loop starts at 1, so 0 is never printed.
Approach
You cannot say in advance how far you need to count: for B = 3 the fifth multiple is 15, for B = 100 it is 500. So the loop cannot be a simple "count to N". Instead, the idea is to walk through the numbers 1, 2, 3, ... one at a time, test each, and stop when enough have been printed.
That takes two counters with different jobs:
currentNumberis the candidate being tested. It goes up by one on every pass.printedSoFarcounts the multiples already printed. It goes up only when a multiple is found.
Since the number of passes depends on the data, a while loop fits better than a for loop: the stopping condition is "printed enough", not "reached a fixed number".
Here is the trace for A = 3, B = 2: candidates 1 (no), 2 (print, count 1), 3 (no), 4 (print, count 2), 5 (no), 6 (print, count 3). The count now equals A, so the loop ends. The output is 2, 4 and 6.
Step by step
- Declare
currentNumberas anintset to 1. This is the first candidate. - Declare
printedSoFaras anintset to 0. Nothing has been printed yet. - Start a
whileloop with the conditionprintedSoFar < A. The loop continues until exactlyAnumbers have been printed, then stops. - Inside the loop, test the candidate with an
ifoncurrentNumber % B == 0. - When the test passes, print the candidate with
Console.WriteLine. - Increment
printedSoFarin the sameifblock, so the count stays in step with the output. - Increment
currentNumberafter theif, still inside the loop. This must happen on every pass, whether or not the candidate was a multiple. Putting it inside theifwould leave the loop stuck on a non-multiple forever.
The solution in C#
class Solution {
public void PrintMultiples(int A, int B) {
int currentNumber = 1;
int printedSoFar = 0;
while (printedSoFar < A) {
if (currentNumber % B == 0) {
Console.WriteLine(currentNumber);
printedSoFar++;
}
currentNumber++;
}
}
}
A few C# details:
- The method is
voidand writes withConsole.WriteLine, which puts each number on its own line. - The parameters are named
AandBin capitals. C# is case-sensitive, soaorbwould be different names that do not exist. - The two counters change at different times:
printedSoFar++is inside theif, andcurrentNumber++is outside it. %on twointvalues gives the remainder as anint. SinceBis positive, the remainder is never negative.
The loop condition and the if answer different questions. The while asks "have I printed enough?", while the if asks "is this number one of the ones I want?". Keeping the two questions apart, and giving each its own counter, is what makes the code easy to follow.
Complexity
The loop looks at every number up to the A-th multiple of B, which is A * B. That makes the time O(A * B). The space is O(1), because only two integers are kept. Printing the multiples directly as B, 2 * B, 3 * B and so on would take only O(A); this lesson uses the counting version to practise while loops with a condition inside.
A shortcut for later
Because the k-th multiple of B is simply k * B, the same output can come from a loop that skips the testing entirely:
for (int k = 1; k <= A; k++) {
Console.WriteLine(k * B);
}
It is shorter and faster, but the lesson's version shows how to combine a condition, two counters and a while loop, which is the skill the exercise practises.
Edge cases and common mistakes
- Incrementing
currentNumberinside theif. When the first candidate is not a multiple, nothing changes, and the loop spins forever. - Using
currentNumberin the loop condition. Comparing it toAstops the loop too early, since the answer reachesA * B. - Forgetting
printedSoFar++. The condition never becomes false, and the program prints without end. - Using
=in place of==.if (currentNumber % B = 0)does not compile in C#, because the condition would not be abool. B = 1. Every number is a multiple, so the output is 1, 2, ...,A.A = 0. The loop condition is false at once and nothing is printed.- Very large inputs.
intoverflows silently in C#, so ifA * Bgoes beyond about 2.1 billion,currentNumberwraps to a negative value. The lesson's inputs stay far below that.
Testing
A = 5, B = 3prints 3, 6, 9, 12, 15.A = 3, B = 1prints 1, 2, 3.A = 1, B = 7prints 7.