We will implement different algorithms to print the Collatz sequence in javascript. Everything will be written in ES6.
A Collatz sequence is obtained by performing the following operations on any given number.
- If the
number
is even thennumber = number / 2
. - If the
number
is odd thennumber = 3 * number + 1
. - Repeat this steps until the number becomes
1
.
n = 6 6, 3, 10, 5, 16, 8, 4, 2, 1
A brute-force method.
Implementation
- We will loop till the given number is equal to
1
. - If the number is even then we will do
number = number / 2
and print it. - Else If the number is odd then we will do
number = 3 * number + 1
and print it.
let collatz = (num) => { // loop till the given num is not 1 while(num != 1){ //print the num console.log(num); //if the number is even if(num % 2 == 0){ num = parseInt(num / 2); }else{ //if the number is odd num = (num * 3) + 1; } } // print the last number console.log(num); }
Input: collatz(5); collatz(11); Output: 5 16 8 4 2 1 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Time complexity: NA.
Space complexity: O(1).
Time and Space complexity
- There is no specific time for this algorithm as it will till the given number is not 1, so Time complexity is NA.
- We are using constant space, so Space complexity is O(1).
With Recursion.
Implementation
- We are going to use an array to store the collatz sequence.
- We will create a function which will call itself recursively if the given number is not
1
. - If the number is even then we will call the same function with
number = number / 2
. - Else if the number is odd then we will call it with
number = number * 3 + 1
. - If the number is
1
then we will return1
.
let collatzTail = (num, store) => { //if num is 1 then store 1 if(num === 1) { store.push(1); return store; //if num is even then store num / 2 } else if(num % 2 === 0) { store.push(num); return collatzTail(parseInt(num / 2), store); //if num is odd then store num * 3 + 1 } else { store.push(num); return collatzTail(3 * num + 1, store); } };
Input: let store = []; collatzTail(6, store); console.log(store); let store = []; collatzTail(10, store); console.log(store); Output: [6, 3, 10, 5, 16, 8, 4, 2, 1] [10, 5, 16, 8, 4, 2, 1]
If you want you can print this array.
Time complexity: NA.
Space complexity: NA.
Time and Space complexity
- There is no specific time to this algorithm because it is condition based, so Time complexity is NA.
- As this is running on condition there can be any number of call stack, so Space complexity is NA.