Start learning free

LESSON 139 OF 414 · LOOPS & CONDITIONALS

Collatz Conjecture in Scala: A while Loop with Mutable State

Practice Read the full explanation

The Collatz conjecture in mathematics asks whether repeating two simple arithmetic operations will eventually transform every positive integer into one. It concerns sequences of integers in which each term is obtained from the previous term as follows:
if the previous term is even, the next term is one half of the previous term.
If the previous term is odd, the next term is 3 times the previous term plus 1.
The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence.

You are given an integer n and you should print to the console all the values that n takes throughout the Collatz Conjecture.

Example:

Input: n = 3

Output:
3
10
5
16
8
4
2
1

Explanation:
n = 3  => n is odd  => n becomes 3 * 3 + 1 = 10
n = 10 => n is even => n becomes 10 / 2    = 5
n = 5  => n is odd  => n becomes 5 * 3 + 1 = 16
n = 16 => n is even => n becomes 16 / 2    = 8
n = 8  => n is even => n becomes 8 / 2     = 4
n = 4  => n is even => n becomes 4 / 2     = 2
n = 2  => n is even => n becomes 2 / 2     = 1
n = 1 => stop

Hints:

Look at the example and notice that we apply a transformation over and over until we reach a final point where we stop. Does that ring a bell?

We need to repeat the transformation code as long as one condition holds (num is greater than 1). How do you write that in code?

We will use a while loop that executes as long as num > 1 . What should we do inside this loop?

If num is even, we should apply a transformation. Otherwise, we should apply the other transformation. How do we handle these different scenarios?

We can do this using an if - else statement.

Video Solution:

STEP 1 OF 6

Guided

Ctrl + Enter to check

SCALA · LOOPS & CONDITIONALS

Collatz Conjecture in Scala, explained

Problem overview

The Collatz sequence starts from a positive integer n and repeats one rule until it reaches 1. If the current term is even, the next term is half of it. If the current term is odd, the next term is three times it plus one. The Collatz conjecture says that every positive starting value eventually reaches 1. Nobody has proved it, but it has held for every number that has been tried.

The method printSeries takes an Int named n and prints every value the sequence takes, starting with n itself and ending with 1. For n = 3 it prints:

3 is odd, so the next term is 3 * 3 + 1 = 10. 10 is even, so it becomes 5, and so on until 2 becomes 1. The sequence stops at 1.

Approach

The same transformation is applied again and again, and nobody knows in advance how many times. When the number of repetitions is not known, a while loop is the right tool: it keeps running as long as a condition holds. Here the condition is "the current value is greater than 1".

The current value changes on every pass, so it needs to live in a variable that can be reassigned. Inside the loop, an if / else chooses between the even rule and the odd rule. The value is printed once before the loop, for the starting term, and once at the end of every pass, for each new term.

Step by step

Copy n into a variable. Method parameters in Scala are immutable, so n can't be reassigned. Declare var num = n and change num instead.
Print the starting value. The sequence begins with n, so println(num) comes before the loop.
Write the loop condition. while (num > 1) keeps going until the value reaches 1. Test num, not n, because only num changes.
Handle the even case. If num % 2 == 0, halve it with num /= 2. Division of two Int values drops the remainder, but an even number has none, so the result is exact.
Handle the odd case. In the else branch, set num = 3 * num + 1.
Print the new term. Put println(num) after the else block and still inside the loop, so it runs for both cases. The final pass prints 1 and then the condition fails and the loop ends.

The solution in Scala

class Solution {
    def printSeries(n: Int): Unit = {
        var num = n
        println(num)
        while (num > 1) {
            if (num % 2 == 0) {
                num /= 2
            } else {
                num = 3 * num + 1
            }
            println(num)
        }
    }
}

Scala details in this solution:

var versus val. A val can't be reassigned, a var can. The loop needs a var because the value changes on each pass. Its type, Int, is inferred from n.
num /= 2 is shorthand. It means num = num / 2. The same pattern works for +=, -= and *=.
Integer division truncates. 7 / 2 is 3 in Scala when both sides are Int. The code only divides even numbers, so nothing is lost.
The result type is Unit. The method prints and returns nothing, so no return is needed.
Int can overflow. Values are 32-bit and wrap around silently on overflow. For small starting values the sequence stays well within range. For n = 113383 the sequence passes the largest Int, 2147483647, and the value goes negative after 120 steps (the value is then -1812855948). The loop condition num > 1 is false for a negative number, so the loop ends right after printing that negative value, and the sequence is wrong. Using Long avoids it: with Long, the sequence for 113383 peaks at 2482111348.

Tracing a second example

For n = 6 the variable num goes through these values: 6 is even and becomes 3; 3 is odd and becomes 10; then 5, 16, 8, 4, 2 and finally 1. The printed lines are 6, 3, 10, 5, 16, 8, 4, 2, 1. The first 6 comes from the print before the loop, and each later line comes from the print at the end of a pass. Once num is 1, the condition num > 1 is false and the method ends.

Edge cases and common mistakes

n = 1. The starting value is printed, the loop condition is false at once and the method prints just 1.
n = 0. It is not a positive integer, but the method handles it without looping forever: it prints 0 and stops, since 0 is not greater than 1.
Printing before the loop only. If the print inside the loop is missing, the output ends with the starting value alone.
Printing the new value in only one branch. If println(num) sits inside the if or the else block, terms from the other case are never printed.
Testing n in the loop condition. Because n never changes, a condition like n > 1 never becomes false for n = 3, and the loop runs forever.
Printing 1 twice or not at all. The value 1 should appear once, as the final term. The condition num > 1, with the print at the end of the pass, does exactly that.

Testing

printSeries(3) prints 3, 10, 5, 16, 8, 4, 2, 1, one per line.
printSeries(1) prints 1.
printSeries(8) prints 8, 4, 2, 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