Problem overview
The function printMultiples(A: Int, B: Int) receives two positive integers. It must print, one per line, the first A positive numbers that are divisible by B. A number X is divisible by B when X % B == 0, that is, when dividing leaves no remainder. The function prints and returns nothing.
For A = 5 and B = 3, the output is 3, 6, 9, 12 and 15. Those are the first five numbers from 1 upward that leave no remainder when divided by 3. The number 0 is also divisible by 3 but is not printed: the counting starts at 1.
Approach: walk the numbers and count what you print
The simplest way to solve this is to look at 1, 2, 3, and so on, one at a time, and print the ones that pass the divisibility test. The question is when to stop. You cannot stop at a fixed number such as 15, because that depends on A and B. You stop when you have printed A numbers.
That gives the loop two pieces of state:
currentNumber, the candidate being checked, which goes up by 1 on every pass.printedSoFar, how many multiples have been printed, which goes up only when one is printed.
A for loop over a range is not a good fit, because the number of candidates is not known in advance: it depends on how far you must look to find A multiples. A while loop fits, with the condition printedSoFar < A.
A shortcut exists: the multiples of B are B, 2 * B, 3 * B and so on, so a loop from 1 to A could print B * i without testing anything. The lesson uses the testing approach, because it practises the remainder test and loop counters.
Step by step
- Declare
currentNumberas avarset to 1. It is the number being examined, and it will change, so it needsvarrather thanval. - Declare
printedSoFaras avarset to 0. Nothing has been printed yet. - Start a
whileloop that runs whileprintedSoFar < A. The loop stops as soon as exactlyAnumbers have been printed. - Add an
ifthat testscurrentNumber % B == 0. The remainder operator%gives what is left after division, and a remainder of 0 means divisible. - Print the number inside the
if.printlnprints the value and ends the line. - Increment
printedSoFarinside theif. It must change only when something was printed. Moving it outside theifwould count every candidate, and the loop would stop too early. - Increment
currentNumberafter theif, still inside the loop. This happens on every pass, whether or not the number was a multiple. If it only happened inside theif, the loop would get stuck on the first number that is not a multiple and run forever.
The solution in Kotlin
class Solution {
fun printMultiples(A: Int, B: Int) {
var currentNumber = 1
var printedSoFar = 0
while (printedSoFar < A) {
if (currentNumber % B == 0) {
println(currentNumber)
printedSoFar++
}
currentNumber++
}
}
}
Kotlin details worth knowing:
- Type inference.
var currentNumber = 1is anIntbecause the literal1is anInt. The type does not have to be written. - Parameter names. The capital
AandBare ordinary parameter names. They are read-only inside the function, which is why the loop counts with its own variables rather than changingA. ++as a statement.printedSoFar++adds 1. Used as a statement on its own line, as here, it needs no result value.- Two counters, two jobs. One variable tracks where you are looking and the other tracks how much you have done. Keeping them separate is what lets the loop skip numbers that fail the test.
Walking through the example
With A = 5 and B = 3, the numbers 1 and 2 give remainders 1 and 2, so nothing is printed and only currentNumber grows. At 3 the remainder is 0, so 3 is printed and printedSoFar becomes 1. The same happens at 6, 9, 12 and 15. After 15 is printed, printedSoFar reaches 5, the loop condition becomes false, and the function returns.
Complexity
Time: O(A * B). The last multiple printed is A * B, and the loop looks at every number up to it, doing constant work each time.
Space: O(1). The function holds two integers and stores nothing else.
Edge cases and common mistakes
- B equal to 1. Every number is divisible, so the output is 1, 2, ..., A.
- B larger than A. Nothing special happens. With
A = 3andB = 10the output is 10, 20 and 30. - Incrementing
currentNumberonly inside theif. The loop hangs at the first non-multiple. - Forgetting
printedSoFar++. The condition stays true forever and the program prints multiples without end. - Starting
currentNumberat 0. Zero passes the test (0 % Bis 0), so 0 would be printed first and everything would shift by one. - Using
=instead of==. In KotlincurrentNumber % B = 0does not compile, because assignment is not an expression. - Large results.
Intis 32 bits. IfA * Bis above 2147483647, the counter wraps around to a negative number silently, and the output is no longer the multiples you expect. - B equal to 0. The statement promises positive integers. A remainder by 0 throws an
ArithmeticException(/ by zero).
Testing
A = 5,B = 3prints 3, 6, 9, 12, 15.A = 3,B = 10prints 10, 20, 30.A = 4,B = 1prints 1, 2, 3, 4.A = 1,B = 7prints 7.