Problem overview
The function printMultiples takes two positive integers, A and B. It must print the first A positive numbers that are divisible by B, one per line. A number is divisible by B when dividing it by B leaves remainder 0, which in Go is x % B == 0.
For A = 5 and B = 3 the output is 3, 6, 9, 12 and 15. The numbers in between, such as 4 and 5, leave a remainder of 1 or 2 when divided by 3, so they are skipped. Zero is also divisible by 3, but the lesson counts from 1, so it isn't printed.
Approach: check numbers one by one
The simplest idea is to walk through 1, 2, 3 and so on, test each number, and print the ones that pass. The difficulty is knowing when to stop. You can't stop at a fixed number such as 15, because that depends on A and B. The stopping rule is about how many numbers have been printed, not how large the current number is.
So the loop needs two variables:
currentNumber, the candidate being tested, which goes up by 1 on every pass;printedSoFar, how many multiples have been printed, which goes up only when one is found.
The loop continues while printedSoFar < A. The pass that prints the A-th multiple raises the counter to A, and the condition fails on the next check.
There is a shortcut: the multiples of B are simply B, 2*B, 3*B and so on, so a loop from 1 to A printing i * B does the same job. This lesson uses the search version, which also works when the rule for a valid number is more complicated than divisibility.
Step by step
- Declare
currentNumberwith:=and start it at 1, the first candidate. - Declare
printedSoFarwith:=and start it at 0, because nothing has been printed yet. - Write the loop. In Go,
forfollowed by only a condition works like awhileloop. The condition isprintedSoFar < A. - Test the candidate inside the loop with an
ifwhose condition iscurrentNumber % B == 0. - Print it with
fmt.Printlninside theif. - Increase
printedSoFar, also inside theif. The counter must only change when something was printed. - Move on to the next candidate by increasing
currentNumber. This line sits after theifbut inside the loop, so it runs on every pass, whether or not the number was a multiple.
The solution in Go
func printMultiples(A int, B int) {
currentNumber := 1
printedSoFar := 0
for printedSoFar < A {
if currentNumber % B == 0 {
fmt.Println(currentNumber)
printedSoFar += 1
}
currentNumber += 1
}
}
The Go details:
- A
forwith only a condition. Go has nowhilekeyword.for condition { }does that job. += 1instead of++. Both work. In Go,x++is a statement that adds 1, written after the variable.- The function returns nothing. The results go to the console, so the signature has no return type.
- Both variables are used. Go refuses to compile an unused local variable, but both appear in conditions and updates here.
- The remainder operator.
%works on integers. BecauseAandBare positive, the result is never negative.
Complexity
Time: O(A * B). The loop looks at every number up to the A-th multiple, which is A * B, so it makes that many passes. The shortcut of multiplying would run in O(A).
Space: O(1). Only two integers are stored, and the numbers are printed rather than saved.
Edge cases and common mistakes
B = 1. Every number is a multiple, so the output is simply 1 up toA.- Moving
currentNumber += 1into theif. The first non-multiple would never be skipped over, and the loop would test the same number forever. - Moving
printedSoFar += 1outside theif. The counter would count every candidate, and the loop would stop afterAnumbers in total instead ofAmultiples. - Starting
currentNumberat 0. Zero passes the divisibility test, so the output would start with 0 and end one multiple earlier than expected. - Looping on
currentNumber < A. That prints multiples belowA, notAof them.
Testing
A = 5,B = 3prints 3, 6, 9, 12, 15.A = 3,B = 1prints 1, 2, 3.A = 1,B = 7prints 7.A = 4,B = 10prints 10, 20, 30, 40.