We will implement an optimized algorithm to print the number with the maximum count of numbers in a Collatz sequence under 1000000 in javascript. Everything will be written in ES6.
Learn more about Collatz sequence.
Implementation
- We will use dynamic programming to solve this.
- We will use a object to store the count of already computed collatz sequence.
- Then loop through all the numbers upto 1000000 and find the collatz sequence of each of them if it is not already computed and store it.
let collatzSequence = () => { let memo = {}; //Store already computed sequence count let max = 0; //Store the max count let index = 0; //Store the number with max count //loop from 1 to 1000000 for(let j = 1; j <= 1000000; j++){ let count = 1; //initialize the count let i = j; // use temp variable to compute the collatz sequence // compute the collatz sequence while(i > 1){ //if the sequence is not already present then compute it if(!memo[i]){ i = (i % 2 == 0) ? parseInt(i / 2) : parseInt((3 * i) + 1); count++; }else{ //Else update the count with already stored sequence count count = count + memo[i] - 1; break; } } //store the sequence for the given number memo[j] = count; //get the max count and number with max count if(max < count){ max = count; index = j; } } //return the number return index; } Input: console.log(collatzSequence()); Output: 837799
Time complexity: NA.
Space complexity: O(1).
Time and Space complexity
- We are iteating from 1 to 1000000 but there is no specific time of computing the collatz sequence of each numbers, so Time complexity is NA.
- We are using constant space of 1000000 to store the sequence count, so Space complexity is O(1).