Start learning free

LESSON 136 OF 410 · LOOPS & CONDITIONALS

Collatz Conjecture in JavaScript (Time Complexity: O(log n))

Practice Read the full explanation

The Collatz conjecture in mathematics asks whether repeating two simple arithmetic operations will eventually transform every positive integer into one. It concerns sequences of integers in which each term is obtained from the previous term as follows:
if the previous term is even, the next term is one half of the previous term.
If the previous term is odd, the next term is 3 times the previous term plus 1.
The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence.

You are given an integer n and you should print to the console all the values that n takes throughout the Collatz Conjecture.

Example:

Input: n = 3

Output:
3
10
5
16
8
4
2
1

Explanation:
n = 3  => n is odd  => n becomes 3 * 3 + 1 = 10
n = 10 => n is even => n becomes 10 / 2    = 5
n = 5  => n is odd  => n becomes 5 * 3 + 1 = 16
n = 16 => n is even => n becomes 16 / 2    = 8
n = 8  => n is even => n becomes 8 / 2     = 4
n = 4  => n is even => n becomes 4 / 2     = 2
n = 2  => n is even => n becomes 2 / 2     => 1
n = 1 => stop
Hints:

Look at the example and notice that we apply a transformation over and over until we reach a final point where we stop. Does that ring a bell?

We need to repeat the transformation code as long as one condition holds (n is greater than 1). How do you write that in code?

We will use a loop that executes as long as n > 1. What should we do inside this loop?

If n is even, we should apply a transformation. Otherwise, we should apply the other transformation. How do we handle these different scenarios?

We can do this using an if - else statement.

Video Solution:

STEP 1 OF 5
    Ctrl + Enter to check

    JAVASCRIPT · LOOPS & CONDITIONALS

    Collatz Conjecture in JavaScript, explained

    Understanding the Problem

    The core challenge of the Collatz Conjecture is to repeatedly apply a set of rules to transform a number until it reaches 1. This problem is significant in mathematics and computer science because it is simple to understand but has not been proven for all positive integers. Common applications include algorithm design and understanding iterative processes.

    Potential pitfalls include not handling the even and odd conditions correctly or not stopping the loop when the number reaches 1.

    Approach

    To solve this problem, we need to repeatedly apply the transformation rules until the number becomes 1. A naive solution would involve a simple loop that checks if the number is even or odd and applies the corresponding transformation.

    However, this naive approach is already optimal for this problem since each step reduces the number significantly, especially when the number is even.

    Algorithm

    1. Start with the given number n.

    2. While n is greater than 1, do the following:

    • If n is even, divide it by 2.
    • If n is odd, multiply it by 3 and add 1.
    • Print the current value of n.

    3. Stop when n becomes 1.

    Code Implementation

    /**
 * Function to print the Collatz sequence for a given number n
 * @param {number} n - The starting integer
 */
function collatzConjecture(n) {
  // Print the initial value of n
  console.log(n);
  
  // Continue the loop until n becomes 1
  while (n > 1) {
    if (n % 2 === 0) {
      // If n is even, divide it by 2
      n = n / 2;
    } else {
      // If n is odd, multiply by 3 and add 1
      n = 3 * n + 1;
    }
    // Print the current value of n
    console.log(n);
  }
}

// Example usage
collatzConjecture(3);

    Complexity Analysis

    The time complexity of this algorithm is O(log n) because, in the worst case, the number of steps required to reduce n to 1 is proportional to the logarithm of n. The space complexity is O(1) since we are using a constant amount of extra space.

    Edge Cases

    Potential edge cases include:

    • n = 1: The sequence should immediately stop.
    • n = 2: The sequence should be 2, 1.
    • Large values of n: The algorithm should handle large values efficiently.

    To test these edge cases, we can run the function with different values of n and verify the output.

    Testing

    To test the solution comprehensively, we can use a variety of test cases:

    • Simple cases: n = 1, n = 2
    • Odd and even numbers: n = 3, n = 4
    • Large numbers: n = 1000000

    We can use JavaScript's built-in console for testing or frameworks like Jest for automated testing.

    Thinking and Problem-Solving Tips

    When approaching such problems, it is essential to:

    • Understand the problem statement and constraints thoroughly.
    • Break down the problem into smaller, manageable parts.
    • Think about edge cases and how to handle them.
    • Practice similar problems to improve problem-solving skills.

    Conclusion

    The Collatz Conjecture is a fascinating problem that is simple to understand but has deep mathematical implications. By understanding and solving this problem, we can improve our algorithmic thinking and problem-solving skills. Practice and exploration of similar problems can further enhance these skills.

    Additional Resources

    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free