Easy–medium · simulation

Collatz Steps

Halve it if it's even, otherwise triple it and add one. Nobody knows whether every number eventually reaches 1 — but your loop can find out for any number you type.

At a glanceApply n = n / 2 when n is even and n = 3n + 1 when it is odd, counting steps until n reaches 1 — n = 1 itself takes 0 steps, which is the case people forget.

Problem

Input: One integer n (1 ≤ n ≤ 100000).

Output: How many steps it takes to reach 1. If n is already 1, print 0.

Samples:

InputOutput
68
10

For 6: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Count the arrows — there are 8, and reaching 1 is the end, not a step of its own.

Your solution

main.cpp — your solution
Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — The rule is a loop body, not a formula

There is no closed form for this — you can't compute the answer, you have to walk it. That's a while loop: keep transforming n, and count one step per transformation.

Hint 2 — Even or odd, one branch each

n % 2 == 0 means even → n = n / 2. Otherwise → n = 3 * n + 1. Integer division is exactly what you want here; there is no remainder to worry about because you already checked it's even.

Hint 3 — Off-by-one lives in the loop condition

Use while (n != 1) and increment inside the body. If you instead start steps at 1, or increment after printing, every single answer is off by one — and n = 1 will print 1 instead of 0.

Solution (try it first!) 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int steps = 0;
    while (n != 1) {
        if (n % 2 == 0) n = n / 2;
        else n = 3 * n + 1;
        steps++;
    }
    cout << steps << endl;
    return 0;
}

This is the Collatz conjecture: start from any positive integer and the sequence always seems to reach 1, but nobody has proved it. Your program is a tiny experiment in mathematics — try 27 and watch it climb to 9232 before it comes down. That habit, simulate the rule and look at the numbers, is how you build intuition for problems with no formula. Keep going with Count the Words.

Deep dive

Why this works

This rule has no formula, so you cannot compute the answer — you have to walk it. Turn the rule into a loop body and the step count into a counter; that's the universal shape for simulation problems.

The cost

O(steps), and nobody can bound the steps in general — which is exactly why the Collatz conjecture is still open. For n ≤ 100000 it stays in the hundreds.

Where it goes wrong

  • Starting steps at 1, or incrementing after printing, makes every answer off by one — and n = 1 prints 1 instead of 0.
  • Writing n > 1 instead of n != 1 looks equivalent for positives, but the moment a typo sends the sequence negative the loop can never end.

Next step

Next, apply "remember the state while you scan" to text: Count the Words.

Two things to remember

  • A rule with no formula becomes a loop body — let the machine do the walking.
  • Reaching the finish is not a step; the loop condition and the counter must agree.
🐞 This version fails — open it and try

steps starts at 1 — every answer is one too high

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int steps = 1;
    while (n != 1) {
        if (n % 2 == 0) n = n / 2;
        else n = 3 * n + 1;
        steps++;
    }
    cout << steps << endl;
    return 0;
}