Start learning free

LESSON 180 OF 414 · LOOPS - CHALLENGES

Print Powers in Scala: A while Loop That Multiplies

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 while loop to repeatedly check if power <= B and if so, print and update power. How will the code look like? 

var power = 1
while (power <= B) {
	println(power)
	power *= A
}


STEP 1 OF 4
    Ctrl + Enter to check

    SCALA · LOOPS - CHALLENGES

    Print Powers in Scala, explained

    Problem overview

    The method printPowers(A: Int, B: Int) must print every power of A that is less than or equal to B, one per line, starting with A to the power 0, which is 1. It returns nothing: the output is what the lesson's tests look at.

    For A = 3 and B = 100 the powers are 1, 3, 9, 27 and 81. The next one, 243, is more than 100, so the method stops there.

    Approach

    You do not need an exponent or a power function. Each power is the previous one multiplied by A, so keep a single variable power that starts at 1. While it is no more than B, print it and multiply it by A. We do not know in advance how many iterations will be needed, which makes while a better fit than a for loop over a fixed range.

    Step by step

    1. Declare power as a var set to 1. The loop changes it, so val would not compile. Scala infers Int from the literal.
    2. Write a while loop whose condition is power <= B. The condition is checked before each pass, so a value above B is never printed.
    3. Print power with println, which puts each value on its own line.
    4. Update power to the next power of A with power *= A. Without this line the loop would print the same number forever.

    The solution in Scala

    class Solution {
    def printPowers(A: Int, B: Int): Unit = {
        var power = 1
        while (power <= B) {
            println(power)
            power *= A
        }
    }
}

    Some Scala details:

    • Unit return type. The method prints and returns nothing useful, which Scala writes as Unit. The body's last expression is the while loop, which also has type Unit, so no return is needed.
    • var versus val. val cannot be reassigned. A variable that a loop updates must be var.
    • *=. Scala has no ++, but it has compound assignments such as += and *=. power *= A means power = power * A.
    • Parentheses on the condition. A while condition goes in parentheses, and the braces hold the body.

    Complexity

    Time: O(log B). The value of power is multiplied by A each pass, so it grows geometrically, and the loop ends after about log of B to the base A iterations. For A = 2 and B = 1000000 that is 20 prints.

    Space: O(1). Only power is stored.

    Edge cases and common mistakes

    • B less than 1. With B = 0 the condition is false at the start, so nothing is printed. This is correct, because even A to the power 0 is 1, which is more than 0.
    • A = 1. power stays at 1, so the loop never ends for any B of at least 1. A = 0 also loops forever when B is at least 1, because power drops to 0 after the first print and stays there. The solution assumes A is at least 2, as in the example.
    • Overflow. Int is 32 bits and overflow wraps silently. If B is close to Int.MaxValue, power *= 2 eventually wraps to a negative number, which is still <= B, so the loop keeps printing instead of stopping. Use a Long for power if the bounds can be that large.
    • Printing after multiplying. Swapping the two lines in the loop prints 3, 9, 27, 81, 243 and misses the first power, 1.
    • Using < instead of <=. A power equal to B must be printed: for A = 3 and B = 27 the last line is 27.

    Testing

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