Problem 14: Longest Collatz sequence efficiency

Problem 14: Longest Collatz sequence efficiency
0

#1

Tell us what’s happening:
I can’t figure out how to solve this efficiently enough for the FCC environment.

First I solved it by brute force, which obviously isn’t efficient enough. Next, I saved an array of objects (number, count) and saved each number as I solved it, then while solving if my working number ever went below the number I was solving I would search the array for the corresponding number and pull the count. Next, I changed the array of objects to store every number I came across, including numbers above the number I was currently solving for, but this meant checking every step of every number against the array of objects. All of these were technically correct algorithms but after ~100, 000 or so would only solve about 1000 numbers per second (by putting if (i % 1000 === 0) {console.log(i)} I could watch in the console). In no case did I wait past 300000 as it was getting pretty slow.

Then, I switched to an array of numbers, where the index is the number being solved and the value stored at that index is the count for that particular index, and storing every number I come across. In my local browser, this solved longestCollatzSequence(1000000) in about 850ms. Since then, I’ve optimized the function in various ways, with the biggest improvement being not storing the count of values above the limit. As it’s presented below, my local browser solves the problem in ~112ms on average. Yet it still fails the last test in FCC and when I console.log the highestIndex, it’s not even close to getting there (usually it logs 106239, sometimes a lower number).

I know it works because in my local environment it produces the correct answer. I’m not sure if this is a deliberate implementation choice by FCC to prevent inefficient solutions, but this is already a LOT more efficient than a brute force method and I feel pretty stuck improving it any further (1ms improvement if I check and store the highestIndex as I go instead of at the end). So anyway, I feel I’m barking up the wrong tree here and need to find a radically faster algorithm (not just small tweaks to what is here), but I don’t want to go google it and have the answer completely spoiled…does anyone have a hint for me??

Your code so far


function longestCollatzSequence(limit) {
  	let arr = [0, 1, 2];//initialize the steps required for 0(n/a), 1(1), and 2(2, 1)
	  //this array stores the number of steps required for number (n) at index n
	  //so for eg. arr[16] will store 5 (16, 8, 4, 2, 1)

  	for (let i = 3; i < limit; i++) {//initialize the rest of the array with falsy value
  		arr.push(0);
  	}

  	for (let i = 3; i < limit; i += 2) {
  		if (!arr[i]) { //if this value is still falsy it hasn't been solved yet
  			let wA = []; //working array, stores new unsolved values in an array
  			let wN = i; //working number
  			do {
  				wA.push(wN); //store this value in working array
  				if (wN % 2 === 1) { //if it's odd
  					wN = (wN * 3 + 1) / 2; //guaranteed to be even next, so do 2 steps
  					wA.push(limit); //push an extra "fake" value to keep count accurate
  				} else { // if it's even
  					wN /= 2;
  				}
  			} while (!arr[wN]) //only do this until you reach an already-solved number

  			let count = wA.length; //we pushed 1 number to wA for each step

  			for (let j = 0, c = count; j < count; j++, c--) { 
  				if (wA[j] < limit) { //don't store values >= limit
  					arr[wA[j]] = c + arr[wN]; //in our result array, in the position we solved for, store the steps taken to reach a known value + the known value
  				}
  			}
  		}
  	}

  	let highestNum = 5;
  	let highestIndex = 16;

  	for (let i = 2; i < limit; i++) { //loop through array and find the highest value
  		if (arr[i] > highestNum) { 
  			highestNum = arr[i];
  			highestIndex = i;
  		}
  	}
	
  	return highestIndex;
}

Your browser information:

User Agent is: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:61.0) Gecko/20100101 Firefox/61.0.

Link to the challenge:
https://learn.freecodecamp.org/coding-interview-prep/project-euler/problem-14-longest-collatz-sequence


Smallest Common Multiple challenge
#2

Would writing a helper function to figure out how many times an even number can be divided by two before it becomes odd (which returns this count and the remaining odd number) help?

If you switch a number into binary format, you can easily determine this by counting the zeros on the right.
Eg
8 is 1000
So it can be divided by 2 three times (count the zeros and leaves us with 1 at the end)
20 is 10100
So it can be divided by 2 two times (and leaves us with 101 which is 5)

164 is 10100100
It can be divided by two two times and leaves us with 101001 which is 41.

You can use a regex to grab the remaining odd value and figure out the number of rhs zeros etc.


#3

Hi, I just tried your idea, but it didn’t work more efficiently, maybe I implemented it wrong:

This is how I implemented it:

function longestCollatzSequence(limit) {
  if(limit < 2) return 1;
  let seq = 1;
  let n = limit;
  for(let i = limit; i >= 2; i--) {
    let j = i;
    let auxSeq = 1;
    while(j > 1) {
      if(j % 2 === 0) {
        let nBinary = j.toString(2);
        let endZeros = nBinary.match(/0+$/)[0].split("").length;
        j = parseInt(nBinary.slice(0,nBinary.length-endZeros), 2)
        auxSeq += endZeros-1;
      }
      else j = j*3 + 1;
      auxSeq++;
    }
    if(auxSeq > seq) {
      seq = auxSeq;
      n = i;
    }
  }
  return n;
}

And this was my previous code:

function longestCollatzSequence(limit) {
  if(limit < 2) return 1;
  let seq = 1;
  let n = limit;
  for(let i = limit; i >= 2; i--) {
    let j = i;
    let auxSeq = 1;
    while(j > 1) {
      if(j % 2 === 0) j /= 2;
      else j = j*3 + 1;
      auxSeq++;
    }
    if(auxSeq > seq) {
      seq = auxSeq;
      n = i;
    }
  }
  return n;
}

This one worked faster, however it wasn’t enough for passing the test in the freecodecamp enviroment.
Which code did you used to pass this problem?
Thanks!


#4

Instead of asking for solutions, see if you can make your own solutions more efficient. We do not want to see threads with loads of solutions, so please do not ask for them.

Thank you.


#5

Try adding consol.log statements above and below the statements you think are taking the longest and log start time and end time. If you can figure out which statment or loop is taking too long you might be able to try different things to optimize it. I have not solved this execise myself. All my comments were suggestions only.


#6

Ps. You don’t need to switch back and forth to binary. Just switch it once at the start and continue with binary form for addition and multiplication etc. Just another suggestion in case it helps.