Find the Length of the Collatz Sequence

Given a positve integer n, find the length of its Collatz sequence. The Collatz sequence is generated sequentially where:
n = n / 2 if n is even
n = 3 * n + 1 if n is odd

And the sequence ends if n = 1

Example 1
Input
n = 11
Output
15
Explanation
The Collatz sequence is: [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] and its length is 15.

Compute the Length of the Collatz Sequence using Iterative Approach

It is proven that the collatz sequence will be eventually be one. Therefore, we can just follow the process and count the steps until it becomes one.

1
2
3
4
5
6
7
8
9
10
11
12

int lengthOfCollatzSequence(int n) {
    int ans = 1;
    while (n != 1) {
        if (n & 1) {
            n = 3 * n + 1;
        } else {
            n >>= 1;
        }
        ans ++;
    }
    return ans;
}

int lengthOfCollatzSequence(int n) {
    int ans = 1;
    while (n != 1) {
        if (n & 1) {
            n = 3 * n + 1;
        } else {
            n >>= 1;
        }
        ans ++;
    }
    return ans;
}

Compute the Length of the Collatz Sequence using Recursion

The problem can be inherently defined recursively thus ideal be implemented as the following Recursive function.

1
2
3
4
5
6
7

int lengthOfCollatzSequence(int n) {
    if (n == 1) return 1;
    if (n & 1) {
        return 1 + lengthOfCollatzSequence(3 * n + 1);
    }
    return 1 + lengthOfCollatzSequence(n / 2);
}

int lengthOfCollatzSequence(int n) {
    if (n == 1) return 1;
    if (n & 1) {
        return 1 + lengthOfCollatzSequence(3 * n + 1);
    }
    return 1 + lengthOfCollatzSequence(n / 2);
}

The base case is when n is one, we return 1 step – because we know eventually all numbers will end up in ONE!

–EOF (The Ultimate Computing & Technology Blog) —