Problem overview
The function print_multiples takes two positive integers, a and b. It prints the first a positive numbers that are divisible by b, one per line, and returns nothing. A number x is divisible by b when x % b == 0.
For a = 5 and b = 3 it prints 3, 6, 9, 12 and 15. Those are the first five multiples of 3. The check starts at 1, so 0, although divisible by everything, is never printed.
Approach
You don't know in advance how far you have to count: the fifth multiple of 3 is 15, but the fifth multiple of 1000 is 5000. A for loop over a fixed range doesn't fit, so the loop must be driven by how many numbers have been printed, not by the number being tested.
That gives two counters. One walks through the candidates 1, 2, 3, and so on. The other counts how many multiples have been printed so far. The loop runs while the second counter is below a. Each pass tests the current candidate and moves on to the next one.
There is a shortcut: the multiples of b are b, 2b, 3b, ..., so a loop over 1..=a printing i * b would also work. This lesson practises the check-and-count pattern, which you will reuse whenever the stopping point depends on what you found instead of on where you are.
Tracing a small case
Take a = 2 and b = 3. At the start current_number is 1 and printed_so_far is 0.
- Candidate 1: 1 % 3 is 1, so nothing is printed. The candidate becomes 2.
- Candidate 2: 2 % 3 is 2, so nothing is printed. The candidate becomes 3.
- Candidate 3: 3 % 3 is 0, so 3 is printed and
printed_so_farbecomes 1. The candidate becomes 4. - Candidates 4 and 5 leave remainders 1 and 2, so nothing is printed.
- Candidate 6: 6 % 3 is 0, so 6 is printed and
printed_so_farbecomes 2. Now2 < 2is false, and the loop ends.
The remainder of a division is always between 0 and b - 1, and it is exactly 0 only for multiples of b. Between two multiples, the remainders count up 1, 2, ..., b - 1.
Step by step
- Declare the candidate as
current_number, withlet mutbecause it changes on every pass, starting at 1. - Declare the counter
printed_so_farthe same way, starting at 0 because nothing has been printed yet. - Write the loop
while printed_so_far < a. When exactlyanumbers have been printed, the condition becomes false and the loop ends. - Test divisibility inside the loop with
current_number % b == 0. - Print the number with
println!inside thatif. - Update the printed counter in the same
if. It must only grow when something was printed. - Advance the candidate after the
ifbut inside thewhile. This line runs on every pass, whether or not the number was a multiple, so the loop always makes progress.
The solution in Rust
impl Solution {
fn print_multiples(a: i32, b: i32) {
let mut current_number = 1;
let mut printed_so_far = 0;
while printed_so_far < a {
if current_number % b == 0 {
println!("{}", current_number);
printed_so_far += 1;
}
current_number += 1;
}
}
}
The Rust details worth knowing:
- Inferred types.
current_numberandprinted_so_farare never given a type. Comparingprinted_so_farwithaand takingcurrent_number % bmake the compiler choosei32for both. - No
++. Rust has no increment operator, so you write+= 1. - Mutability is explicit. Without
mut,current_number += 1is a compile error. Variables are read-only by default. println!is a macro. The!marks it, and the{}placeholder is replaced by the value after the format string.- No return value. The function has no
->type, so it returns(). The last statement in the body ends with a semicolon, and nothing else is needed.
Complexity
Time: the loop tests candidates 1, 2, 3, ... until it has printed a multiples. The a-th multiple is a * b, so the loop makes a * b passes: O(a * b). Iterating over 1..=a and printing i * b would make only a passes.
Space: O(1). Only two integers are stored.
Edge cases and common mistakes
- Forgetting to advance
current_number. The loop tests the same candidate forever and never finishes. - Putting
current_number += 1inside theif. After the first candidate that isn't a multiple, nothing changes any more and the loop never ends. Forb = 3it would hang at the candidate 1. - Counting the wrong thing. Incrementing
printed_so_faron every pass instead of only on a print stops the loop too early and prints fewer thananumbers. - Starting at 0. The candidate 0 is divisible by
b, so it would be printed as a multiple. b = 0. The lesson promises positive inputs. Forb = 0,current_number % bpanics with "attempt to calculate the remainder with a divisor of zero".- Large products. The values are
i32. Witha = 3andb = 1000000000, the function prints 1000000000, 2000000000 and then-2000000000, because the candidate wrapped past the largesti32in an optimized build.
Testing
a = 5,b = 3prints 3, 6, 9, 12, 15.a = 3,b = 1prints 1, 2, 3.a = 0,b = 4prints nothing.
