DSA Factory
Free lessonsProgramming basics · Stage 4 · Loops that wait · Step 3

When you can't predict the length

Follow a rule until you reach the end, even though you can't tell how long it takes. About 9 minutes.

Follow the rule

Here is a famous game. Pick any whole number. If it is even, halve it. If it is odd, triple it and add 1. Then do the same again with the new number, and carry on until you reach 1.

Start with 6: it goes 6, 3, 10, 5, 16, 8, 4, 2, 1. That's 8 steps. Start with 7 and it takes 16 steps. Nobody has found a formula that tells you how many steps there will be in advance. You just follow the rule.

No formula? Run the rule in a while loop and count the steps.
Starting at 6
6
0
3
1
10
2
5
3
16
4
8
5
4
6
2
7
1
8
n
n
6
steps
0

Start at 6. It is even, so halve it.

Move 1 of 7

A loop that decides as it goes

This is where a while loop shines. A for loop needs to know its length at the start. But here only the numbers themselves tell you when to stop.

So the loop condition is simply "not at 1 yet". Inside, you choose between two updates with an if and else, and count each step. Always check that your loop is heading towards its end. Here every number is eventually brought back to 1.

Ask yourself: does every pass bring the loop closer to ending?
In code
steps = 0
while n != 1:
    if n % 2 == 0:
        n = n // 2
    else:
        n = 3 * n + 1
    steps = steps + 1
Quick check

Start with 4 and follow the rule (even: halve it; odd: triple it and add 1) until you reach 1. How many steps does that take?

  1. A2
  2. B3
  3. C1
Show the answer

2. 4 becomes 2, and 2 becomes 1. That is two steps.

Your problem

Steps to reach 1

Start with a number n. If it is even, halve it. If it is odd, triple it and add 1. Repeat until you reach 1, and return how many steps that took. If n is already 1, the answer is 0.

Example
n = 6 → 8

1 ≤ n ≤ 10,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding