Collatz Sequence Steps Bloomberg Python Interview Question

Given a positive integer $n$, the Collatz sequence for $n$ is generated by repeatedly applying the following operations:

1. If $n$ is even, then $n = n / 2$.
2. If $n$ is odd, then $n = 3 * n + 1$.
3. Repeat the above steps until $n$ becomes 1.

Your task is to return the number of steps required to reduce $n$ to 1.

Example #1

Input: $n = 3$

Output: 7

Explanation:

The output is 7, because there were 7 Collatz steps taken:

3 ─> 10 ─> 5 ─> 16 ─> 8 ─> 4 ─> 2 ─> 1

Here's the math behind the 7 steps:

1. Given 3 is odd, so $3 * n + 1 = 10$

2. Given 10 is even, so $n / 2 = 5$

3. Given 5 is odd, so $3 * n + 1 = 16$

4. Given 16 is even, so $n / 2 = 8$

5. Given 8 is even, so $n / 2 = 4$

6. Given 4 is even, so $n / 2 = 2$

7. Given 2 is even, so $n / 2 = 1$

Here's an iterative solution that repeatedly applies the Collatz operations until the given number becomes 1, incrementing a count for each operation performed.

Recursive approach

Not Just at Facebook, but other tech companies too, interviewer ask you to solve the question using multiple approaches. Or at least mention the different althernatives.

Here is a recursive solution to calculate the Collatz Steps;

In case you are not familiar with Recursion, you can find more information here