Problem overview
The method printMultiples(A, B) receives two positive integers. It must print, one per line, the first A positive numbers that are divisible by B. A number is divisible by B when dividing it by B leaves no remainder, that is, when number % B is 0.
In the example, A = 5 and B = 3. The method prints 3, 6, 9, 12 and 15. These are the first five multiples of 3, and they are not the numbers up to 5: A says how many numbers to print, not how far to count.
Approach: two counters, one loop
We do not know in advance where the fifth multiple of 3 will be. For a multiple of 3 it is 15, but for other values of B it is somewhere else. So a loop that counts up to a fixed limit does not fit. The loop has to run until A numbers have been printed, however far that takes.
That suggests two variables:
- one that walks through the candidate numbers 1, 2, 3, and so on;
- one that counts how many multiples have been printed so far.
A while loop that runs as long as the second counter is below A then does the job. On each pass it asks whether the current candidate is divisible by B. If it is, the number is printed and the printed counter goes up by one. Either way, the candidate moves on to the next number.
Another way would be to skip the divisibility test altogether and print B, 2 * B, 3 * B, up to A * B with a for loop. This lesson uses the testing approach, because it practises the remainder operator and a loop whose length depends on a condition rather than a known count.
Step by step
- Declare
currentNumberand set it to 1. It is the candidate being checked. - Declare
printedSoFarand set it to 0. It counts the numbers printed so far. - Write a
whileloop that runs whileprintedSoFar < A. The loop ends right after theA-th number is printed, which is why a strict "less than" is used. - Test divisibility inside the loop with
currentNumber % B == 0. - Print the number inside the
ifwithconsole.log. - Increase
printedSoFarin the sameif, because a number has just been printed. - Increase
currentNumberafter theif, still inside the loop, so that it happens on every pass, whether or not the candidate was printed.
The solution in TypeScript
class Solution {
printMultiples(A: number, B: number): void {
let currentNumber: number = 1;
let printedSoFar: number = 0;
while (printedSoFar < A) {
if (currentNumber % B == 0) {
console.log(currentNumber);
printedSoFar++;
}
currentNumber++;
}
}
}
For A = 5 and B = 3 the candidate runs through 1, 2, 3, 4, and so on. The values 3, 6, 9, 12 and 15 pass the test and are printed. After 15, printedSoFar is 5, the condition 5 < 5 is false, and the loop ends.
Some TypeScript details:
numberfor everything. TypeScript has a single type for integers and decimals, soA,Band both counters are plainnumbervalues. Whole numbers are exact up to 2^53, which is far more than the loop will reach.voidreturn type. The method prints and returns nothing, so it is declared: void.==and===. Here both sides are numbers, socurrentNumber % B == 0behaves like the strict version. In new code===is the usual habit, because it never converts types.%is the remainder. For positive operands it gives what you expect:4 % 3is 1 and9 % 3is 0.
Complexity
Time: O(A * B). The candidate has to reach A * B, the A-th multiple, and each candidate costs a constant amount of work. Counting by candidates therefore takes A * B passes.
Space: O(1). Only two counters are stored. The numbers are printed, not collected.
The alternative loop that prints i * B for i from 1 to A only needs O(A) passes, because it jumps straight from one multiple to the next. Testing every number is simpler to reason about, and it is fast enough for modest inputs.
Edge cases and common mistakes
B = 1. Every number is divisible by 1, so withA = 4the method prints 1, 2, 3 and 4.Blarger than the first multiples. WithA = 3andB = 7the output is 7, 14 and 21. The loop passes through many candidates without printing.- Forgetting to increase
currentNumberon every pass. If the increment is placed inside theif, the candidate stops moving as soon as it fails the test, and the loop runs forever. - Forgetting to increase
printedSoFar. The condition never becomes false, so the method prints multiples without end. - Counting candidates instead of printed numbers. A loop like
while (currentNumber <= A)prints the multiples ofBup toA. ForA = 5andB = 3it prints only 3. - Starting at 0. Zero is divisible by every
B, because0 % 3is 0. Starting there would print 0 as the first line. The task wants positive multiples, so the start is 1.
Testing
A = 5, B = 3prints 3, 6, 9, 12, 15.A = 4, B = 1prints 1, 2, 3, 4.A = 3, B = 7prints 7, 14, 21.A = 1, B = 10prints 10.