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