Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Simulate the rule — even → n/2, odd → 3n+1 — counting steps until you reach 1. That's O(steps) per query with O(1) space. If you must answer many queries, memoize each number's step count in a cache so shared tails are computed once.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you translate the rule into a clean loop, handle the n = 1 base case, and use a 64-bit type because intermediate values can exceed the starting number by orders of magnitude.
Where candidates slip
Using a 32-bit int and overflowing on the 3n+1 spike, being off-by-one on whether the terminal 1 counts, or assuming the value only ever decreases.
How to stand out
Note that 3n+1 on an odd number is always even (so the next step halves it), and offer memoization the moment the interviewer mentions many queries — explaining that sequences share long common tails.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCollatz step countOne query or many?OneManyExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Direct Simulation (Baseline / single query)
1Hint 1Explore hintHide hint
The rule is fully deterministic. What's the smallest state you need to carry while you apply it repeatedly?
2Hint 2Explore hintHide hint
A loop that runs while n != 1: branch on parity, update n, and increment a counter.
3Hint 3Explore hintHide hint
Watch the type: 3n + 1 on a large odd n can exceed a 32-bit int even though the sequence eventually shrinks.
A · Core idea
Carry the current value and a step counter. While the value isn't 1, branch on parity — halve it if even, otherwise compute 3n + 1 — and bump the counter. Return the counter when you land on 1.
Why a 64-bit type is non-negotiable. The sequence does not decrease monotonically. Each odd step multiplies by 3 (plus 1), so values can climb far above the starting n before they eventually fall. Starting at 27 (a small number) the sequence peaks at 9232; for larger starts the peak can blow past 2³¹. Use long in Java (Python ints are unbounded) or you'll silently overflow on the way up and compute garbage.
Why the n = 1 base case matters. The loop condition is while n != 1. If you instead wrote while n > 1 you'd be fine, but a do/while or an off-by-one in the counter is the usual bug — be explicit that reaching 1 ends the process and that length(1) = 0.
Why odd steps don't stall. 3n + 1 where n is odd is always even (odd×odd is odd, plus 1 is even), so the immediately following step halves it. That's why the sequence makes net progress despite the upward jumps — and it's a tidy fact to mention. Some implementations fuse these two steps as (3n + 1) / 2 for a constant speedup.
Why there's no formula. Whether every n even reaches 1 is the unproven Collatz conjecture, so there's no closed-form step count — simulation is the only correct approach. Don't claim a polynomial bound on the step count; report it honestly as O(steps).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 6Array state
start
begin at 6
8C · Code with teaching comments
Reference implementation previewpublic int collatzLength(long n) { if (n < 1) { throw new IllegalArgumentException("n must be positive"); } int steps = 0;Explore the full codeHide the full code
D · Why it works and complexityO(steps to reach 1) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The values rising above the start is the whole gotcha. Treat the step count as the output, pick an integer type wide enough for the spike, and the loop is otherwise mechanical.
ComplexityO(steps to reach 1) time, O(1) space — Each iteration does O(1) work and the loop runs once per step in the sequence. The number of steps (the 'total stopping time') is the output itself — there's no closed form, so we report O(steps). Only the counter and current value are stored.
E · Edge cases and pitfalls3Using int instead of long and overflowing on the 3n+1 spike.Explore edge casesHide edge cases
Pitfalls
- Using int instead of long and overflowing on the 3n+1 spike.
- Off-by-one on whether the terminal 1 counts as a step.
- Assuming the value only decreases — odd steps push it up.
Approach 2 of 2 · Optimal
Memoized Step Counts (Optimal for many queries)
1Hint 1Explore hintHide hint
Different starting numbers funnel into the same tail, e.g. everything that hits 16 then follows 16 → 8 → 4 → 2 → 1. How do you avoid recomputing that tail every time?
2Hint 2Explore hintHide hint
Define length(n) = 1 + length(next(n)) with length(1) = 0, and cache each result in a map.
3Hint 3Explore hintHide hint
Once a value is cached, any future sequence that reaches it stops immediately and reuses the stored count.
A · Core idea
Frame the length recursively: length(n) = 1 + length(next(n)), with length(1) = 0. Cache each n → steps result so any sequence that later passes through n reuses it instead of recomputing the whole tail.
Why memoization pays off across queries. Collatz sequences are like rivers flowing into a common delta: a huge number of starting values eventually hit a power of two and ride … → 16 → 8 → 4 → 2 → 1 down. Without a cache, every query re-walks that shared tail. With a cache, the first sequence to reach 16 records its distance to 1, and every later sequence that touches 16 stops there and adds the stored value. The redundant work collapses.
Why the recurrence is correct. Reaching 1 from n is exactly one step (to next(n)) plus the cost of reaching 1 from next(n). The base case length(1) = 0 grounds the recursion. Because the conjecture (empirically) terminates for all tested n, the recursion bottoms out — though for safety against very deep chains you can implement it iteratively and back-fill the cache, or guard recursion depth.
Why a single query doesn't need this. For one starting value there are no shared tails to reuse — the cache just adds memory and overhead. Reach for memoization only when you're answering many queries (the classic 'longest Collatz sequence under one million' problem), and say so explicitly so the interviewer sees you match the tool to the workload.
Why values can exceed the cache's intended range. A sequence starting below N can climb above N mid-flight. That's fine — you still cache those larger values; they're computed once and help future queries too.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
queries for n = 8 then n = 6, sharing the tail at 8Interactive diagram
Shared tails reused from the cache
length(8)Once 8 → … → 1 is cached, the sequence from 6 stops at 8 and adds the stored count.
8C · Code with teaching comments
D · Why it works and complexityO(total distinct steps) amortized timeO(distinct values cached) spaceOpen the invariant and proofExplore the proofHide the proof
The optimization isn't a cleverer rule — it's noticing that many sequences share suffixes, so the step count is a textbook overlapping-subproblem candidate. Cache n → steps and the redundant tail-walking disappears.
ComplexityO(total distinct steps) amortized time, O(distinct values cached) space — Each distinct value's step count is computed exactly once and stored; subsequent encounters are O(1) lookups. Across many queries the total work is proportional to the number of distinct values ever visited, not the sum of every sequence length.
E · Edge cases and pitfalls6n = 1 — Base case returns 0 immediately without recursing.Explore edge casesHide edge cases
Edge cases handled
n = 1Base case returns 0 immediately without recursing.repeated query for the same nSecond call is an O(1) cache hit.n climbs above its starting rangeLarger intermediate values are cached too and speed up later queries.
Pitfalls
- Deep recursion blowing the stack on long chains — use iteration + back-fill if needed.
- Caching with a 32-bit key/value and overflowing on the climb.
- Adding a cache for a single query, where it only costs memory.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewprivate final Map<Long, Integer> cache = new HashMap<>(); public int collatzLength(long n) { if (n == 1) { return 0;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
132-bit overflow on the climb
3n+1 can push the value above Integer.MAX_VALUE even when the starting n is small, producing a wrong (negative) value.
Explore the code comparisonHide the code comparison
32-bit overflow on the climb
3n+1 can push the value above Integer.MAX_VALUE even when the starting n is small, producing a wrong (negative) value.
Don't write this
int n = start;
while (n != 1) {
n = (n % 2 == 0) ? n / 2 : 3 * n + 1; // overflows int
steps++;
}Write this instead
long n = start;
while (n != 1) {
n = (n % 2 == 0) ? n / 2 : 3 * n + 1;
steps++;
}2Off-by-one on the terminal 1
Counting the arrival at 1 as an extra step (or starting steps at 1) gives a length one too large. length(1) must be 0.
Explore the code comparisonHide the code comparison
Off-by-one on the terminal 1
Counting the arrival at 1 as an extra step (or starting steps at 1) gives a length one too large. length(1) must be 0.
Don't write this
steps = 1 # wrong starting count
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1
return stepsWrite this instead
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1
return steps3Assuming monotonic decrease
Odd steps multiply by 3, so the sequence rises before falling. Logic that breaks early 'because it's decreasing' is wrong.
Explore the code comparisonHide the code comparison
Assuming monotonic decrease
Odd steps multiply by 3, so the sequence rises before falling. Logic that breaks early 'because it's decreasing' is wrong.
Don't write this
while n > prev: # bogus: the value goes up on odd steps
...Write this instead
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1Revise
Carry the pattern into the interview
Pattern to remember
Direct simulation of the Collatz map, optionally memoized for repeated queries
Code pattern to memorize
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3*n + 1
steps += 1
return stepsRules to remember
- 1Decide whether the count includes the final
1. Convention:length(1) = 0steps (you're already there). State your choice. - 2Use a 64-bit type — the
3n + 1rule makes intermediate values spike far above the startingn(e.g. 27 peaks at 9232). - 3
n = 1is the base case: zero steps. Don't let the loop run on it. - 4The odd branch
3n + 1is always even, so the very next step halves it — a common micro-fact interviewers like. - 5For many queries, memoize
n → steps; recursion onnext(n)lets every cached tail short-circuit the rest.
Use this pattern when
- You're asked for the stopping time / step count of the Collatz (3n+1) process
- Counting iterations of any deterministic 'apply rule until fixed point' process
- Batched queries over a range of starting values (memoization shines)
- Demonstrating you reason about overflow on a process whose values can balloon
Choose another pattern when
- You need to *prove* every n reaches 1 → that's the open Collatz conjecture, not a coding task
- Single query, tiny n → plain simulation; a cache is needless overhead
- You need the peak value, not the length → track a max instead of (or alongside) the counter
Interview takeaway
Collatz length is pure simulation — the interview substance is (1) using a wide enough integer because 3n+1 makes values spike, and (2) recognizing that overlapping tails across many queries justify memoization.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternDeterministic simulation with optional memoization. The single-query version is a clean loop; the batched version is a textbook overlapping-subproblems cache (n → steps). The transferable lesson: when many inputs share suffixes of work, memoize the suffix.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Longest Collatz sequence under NFind the starting value below N with the most steps — memoization across queries is the intended speedup.
- Happy NumberAnother 'apply a rule repeatedly' process; here you detect a cycle instead of counting to 1.
- Power of Two checkThe tail of every Collatz sequence rides a power of two down to 1 — bit tricks identify those quickly.