Start learning free

LESSON 183 OF 414 · LOOPS - CHALLENGES

Print Powers in Rust: Loop with a Running Product

Practice Read the full explanation

Given two non-negative integers A and B, print to the console all numbers less than or equal to B that are powers of A

Powers of a number are: A0, A1, A2, etc.

An = A multiplied by itself n times

A0 = 1
A1 = A
A2 = A * A
A3 = A * A * A
A4 = A * A * A * A
etc.

Example:

Input: A = 3, B = 100

Output:
1
3
9
27
81

Explanation:
30 = 1
31 = 3
32 = 9
33 = 27
34 = 81
Hints:

We start with the integer 1. We should repeatedly do some instructions (print it then multiply it by A) as long as one condition is satisfied (current power <= B). Sounds familiar?

We should use a variable power, initially equal to 1, in order to store the current power. And we should use a loop (a while loop, or in languages without one a condition-only for loop) to repeatedly check if power <= B and if so, print and update power. How will the code look like?

Set power to 1. While power is less than or equal to B: print power, then multiply power by A.

STEP 1 OF 4
    Ctrl + Enter to check

    RUST · LOOPS - CHALLENGES

    Print Powers in Rust, explained

    Problem overview

    The function print_powers takes two non-negative integers, a and b, and prints every power of a that is less than or equal to b, one per line, from the smallest. The function returns nothing; its result is the printed text. The powers of a are a⁰ = 1, a¹ = a, a² = a * a, and so on.

    In the example, a = 3 and b = 100. The powers of 3 are 1, 3, 9, 27, 81 and then 243, which is above 100. The output is:

    1
3
9
27
81

    Approach

    There is no need to compute aⁿ from scratch for each exponent. Each power is the previous one times a: 1, then 1 * 3 = 3, then 3 * 3 = 9, and so on. So one variable can hold the current power, and we update it after each print. We do not know in advance how many powers there are, which makes a while loop a better fit than a for loop: keep going as long as the current power does not exceed b.

    Because the powers of any a greater than 1 at least double each time, the loop runs about log of b times. For a = 3 and b = 100 it runs 5 times, and even for b near two billion with a = 2 it runs about 31 times.

    Step by step

    1. Declare the current power. It starts at 1, because a⁰ = 1, and it must be mut because the loop changes it. The compiler infers i32 from the comparison with b and from the multiplication by a.
    2. Write the loop condition. The loop runs while power <= b. Using <= and not < matters, because a power equal to b must be printed too.
    3. Print inside the loop. println! takes a format string first, and "{}" is the placeholder that gets replaced with power.
    4. Move to the next power. Multiply power by a with *=. This must happen after the print, otherwise the first line would be a and not 1.

    Printing before multiplying is the reason the check happens at the top of the loop: each value is tested against b before it is printed, so a power above b is never shown.

    The solution in Rust

    impl Solution {
    fn print_powers(a: i32, b: i32) {
        let mut power = 1;
        while power <= b {
            println!("{}", power);
            power *= a;
        }
    }
}

    Rust details worth knowing here:

    • println! ends in an exclamation mark because it is a macro, not a function. The format string comes first, and each {} takes the next argument.
    • Variables are immutable by default. Without mut, the line power *= a would not compile.
    • The function has no return type, so it returns the unit value (). That is what a function that only prints looks like.

    Complexity

    For a ≥ 2, the loop runs once per power of a not above b, which is about log base a of b plus one iterations. So the time is O(log b). The function uses one extra variable, so the space is O(1).

    Edge cases and common mistakes

    • b smaller than 1. With b = 0 the condition 1 <= 0 is false at once, and nothing is printed. With b = 1 exactly one line, 1, is printed.
    • a = 1. Every power is 1, so with b ≥ 1 the condition never becomes false and the loop never ends. It prints 1 forever.
    • a = 0. The powers go 1, 0, 0, 0, and so on. After printing 1, power becomes 0, which is not above any non-negative b, so 0 is printed forever. Inputs like these need a guard if they can occur, for example returning after the first print when a is 0 or 1.
    • Overflow. An i32 holds values up to 2147483647. With a = 2 and b = 2147483647, the power 1073741824 is printed and the next product, 2147483648, does not fit. In the optimized build the lessons use, the multiplication wraps around to -2147483648, which is still at most b, so a negative number is printed and then 0 forever. A debug build panics at that multiplication instead. A safe version uses power.checked_mul(a), which returns None on overflow, or compares in i64.
    • Using < instead of <=. The power equal to b would be missing. With a = 3 and b = 81, the last line should be 81.
    • Multiplying before printing. The output would start at a and miss the 1.

    Testing

    • a = 3, b = 100 prints 1, 3, 9, 27, 81.
    • a = 2, b = 0 prints nothing.
    • a = 5, b = 1 prints just 1.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free