Problem overview
The method printMultiples(A: Int, B: Int): Unit receives two positive integers. It prints the first A positive numbers that are divisible by B, one per line. It returns nothing: the result is the console output.
A number X is divisible by B when X % B == 0, that is, when dividing leaves no remainder. In the example, A = 5 and B = 3. The multiples of 3 are 3, 6, 9, 12, 15 and so on, and the first five of them are printed:
3
6
9
12
15
Approach: scan upward and count what you print
You don't know in advance how far you must go to find A multiples, so there is no natural range to loop over. The simple method is to try the numbers 1, 2, 3, ... in order, test each one with %, and print the ones that pass. A second counter records how many have been printed, and the loop stops when that counter reaches A.
This uses two separate variables for two separate jobs. One is the number being tested, and it goes up on every pass. The other is the number of multiples found so far, and it goes up only when a multiple is printed. A while loop suits this, because the stopping rule depends on the count and not on a fixed number of passes.
There is a shortcut: the multiples of B are B, 2 * B, 3 * B, and so on, so a loop over 1 to A printing i * B does the same job. This lesson practises the scan-and-count pattern, which also works when the test is more complicated than divisibility.
Step by step
- Declare the number being tested.
var currentNumber = 1starts the scan at the first positive integer. It is avarbecause it changes on every pass. - Declare the count.
var printedSoFar = 0starts at zero because nothing has been printed yet. - Loop until enough are printed. The condition
printedSoFar < Akeeps the loop going while fewer thanAmultiples have been printed. When the count reachesA, the condition is false and the loop stops. - Test for divisibility. Inside the loop, an
ifcheckscurrentNumber % B == 0. - Print the multiple with
println(currentNumber)inside theif. - Count it. Still inside the
if, add 1 toprintedSoFarwith+= 1. Scala has no++operator. - Move to the next number. After the
if, but still inside the loop, add 1 tocurrentNumber. This line must run on every pass, whether or not the number was a multiple. If it sat inside theif, the first number that wasn't a multiple would be tested again and again, and the loop would never end.
For A = 5 and B = 3, the numbers 1 and 2 fail the test, 3 passes and is printed, 4 and 5 fail, 6 passes, and so on. The count reaches 5 when 15 is printed, and the loop ends there. currentNumber is then 16, but nothing is printed for it.
The solution in Scala
class Solution {
def printMultiples(A: Int, B: Int): Unit = {
var currentNumber = 1
var printedSoFar = 0
while (printedSoFar < A) {
if (currentNumber % B == 0) {
println(currentNumber)
printedSoFar += 1
}
currentNumber += 1
}
}
}
The Scala details worth a closer look:
Unitas the return type.Unitis Scala's "nothing useful" type, likevoidin other languages. The method's work is the printing, so it returns nothing.varandval. Both counters change, so they arevar. Avalcan't be reassigned, and+=on it is a compile error.- The parameters are values.
AandBcan't be reassigned inside the method, which is why the code counts upward with its own variable instead of reducingA. %is the remainder. On non-negativeIntvalues,6 % 3is 0 and7 % 3is 1.- Newlines.
printlnends each output with a line break, which gives one number per line.
Complexity
Time: O(A * B). The last multiple printed is A * B, and the scan visits every number from 1 up to it, doing a constant amount of work for each. Looping over 1 to A and printing i * B would take O(A).
Space: O(1). The method keeps two integers however large A and B are.
Edge cases and common mistakes
B = 1. Every number is a multiple, soprintMultiples(3, 1)prints 1, 2 and 3.Blarger thanA. This changes nothing:printMultiples(2, 10)prints 10 and 20.- Counting every pass. If
printedSoFarwere increased outside theif, the loop would stop afterAnumbers were tested, notAmultiples were printed. - Stopping at
Ainstead of counting. A condition such ascurrentNumber <= Awould test the numbers up toAand print only those that happen to be multiples. - Starting at 0. Zero is divisible by every
Band would be printed first, which gives a different output from the example. - Overflow.
Intis 32 bits, so a productA * Babove 2,147,483,647 would makecurrentNumberwrap to a negative value. The lesson's inputs are small enough to avoid this.
Testing
A = 5, B = 3prints 3, 6, 9, 12 and 15.A = 3, B = 1prints 1, 2 and 3.A = 1, B = 7prints 7.A = 4, B = 5prints 5, 10, 15 and 20.
