Problem overview
The method printMultiples(_ A: Int, _ B: Int) receives two positive integers. It must print the first A positive numbers that are divisible by B, one per line. It returns nothing; the output is what the lesson's tests look at.
A number X is divisible by B when X % B == 0. With A = 5 and B = 3 the method prints 3, 6, 9, 12 and 15. The search starts at 1, and 0, although divisible by everything, is not printed.
Approach: walk the numbers and count the hits
The multiples of B are B, 2B, 3B and so on, so you could compute them directly with a loop from 1 to A. This lesson does something more general: it walks through 1, 2, 3, ... and tests each number with the remainder operator. Two values are needed, and they change at different rates:
- the number being examined, which goes up on every pass;
- how many multiples have been printed, which goes up only when a number is divisible.
The loop must run until the second value reaches A. Because it is impossible to know in advance how many numbers must be examined, a while loop on the count fits better than a for loop over a fixed range. For A = 5 and B = 3 the numbers 1 to 15 are examined, and 5 of them are divisible.
Step by step
- Declare the number to check. A
varnamedcurrentNumberstarts at 1, the first positive number. - Declare the counter. A
varnamedprintedSoFarstarts at 0, since nothing is printed yet. - Loop while
printedSoFar < A. When the counter equalsA, the job is done and the loop ends. Testing the counter, not the number, is what makes the loop stop after exactlyAprints. - Test divisibility inside the loop. An
ifchecks whethercurrentNumber % B == 0. - Print the number inside the
if. - Increase the counter inside the
if, right after the print. Only printed numbers are counted. - Move to the next number after the
ifbut still inside the loop, so it happens on every pass, divisible or not.
A worked trace
Take A = 2 and B = 4. The loop starts with currentNumber = 1 and printedSoFar = 0. Numbers 1, 2 and 3 are not divisible by 4, so only currentNumber grows. At 4, the remainder is 0: the method prints 4 and printedSoFar becomes 1. Numbers 5, 6 and 7 are skipped. At 8 it prints 8 and printedSoFar becomes 2. The condition 2 < 2 is now false, so the loop ends. The output is 4 and 8.
A shortcut for this particular task
Since the multiples of B are B, 2 * B, 3 * B and so on, a loop that visits each of the first A multiples directly also works and runs in O(A):
func direct(_ A: Int, _ B: Int) {
for k in 1...A {
print(k * B)
}
}
Called as direct(5, 3) it prints 3, 6, 9, 12, 15. It needs A to be at least 1, because the range 1...0 is not valid and crashes. The lesson's version practises a while loop with two counters and an if, which is the pattern needed when no formula is available.
The solution in Swift
class Solution {
func printMultiples(_ A: Int, _ B: Int) {
var currentNumber = 1
var printedSoFar = 0
while printedSoFar < A {
if currentNumber % B == 0 {
print(currentNumber)
printedSoFar += 1
}
currentNumber += 1
}
}
}
Swift details worth knowing:
- No
++. Swift has no increment operator, so counters go up with+= 1. - The underscores. In
_ A: Int, the underscore means callers write no argument label:printMultiples(5, 3), notprintMultiples(A: 5, B: 3). varversuslet. Both counters change, so they arevar. Aletwould not compile when the code increments it.- No parentheses needed. Swift conditions are written without parentheses, but the braces are required.
printadds a newline, so each multiple lands on its own line.- The remainder.
%onInttruncates toward zero, but with positive numbers that makes no difference here.
Complexity
Time: O(A * B). The loop examines every number up to A * B, the last multiple it prints, and each examination takes constant time.
Space: O(1). Only the two counters are stored.
Edge cases and common mistakes
B = 1. Every number is divisible, soprintMultiples(3, 1)prints 1, 2 and 3.- Looping on
currentNumber. A condition likecurrentNumber < Awould stop after examiningAnumbers instead of printingAmultiples, and print too few. - Moving the number update into the
if. The number would stay at 1 whenever 1 is not divisible, and the loop would never finish. - Counting every pass. If
printedSoFarwere increased outside theif, the loop would stop afterAnumbers whether or not they were multiples. - Large
B. The loop doesA * Bpasses, so a very largeBmeans many passes before the last multiple. Each pass is cheap, but the work does grow with the product. A = 0. The loop condition is false at once and nothing is printed.
Why the loop cannot stop early or late
The condition is checked before every pass. After the pass that prints the A-th multiple, printedSoFar equals A, so the next check fails and no extra number is printed. Because the update of currentNumber sits outside the if, the loop always makes progress toward the next multiple.
Testing
printMultiples(5, 3)prints 3, 6, 9, 12, 15.printMultiples(3, 1)prints 1, 2, 3.printMultiples(0, 4)prints nothing.
