On the hints page: blurred as a spoiler
both solutions are using check for odd/even like this
arrFib.filter(x => x % 2 != 0)
Maybe it’s worth mentioning on the hints page, that when dealing with Fibonacci numbers one could use this property:
Every third number of the sequence is even
relevant wiki, check out divisibility properties section
in order to do some filtering like this, for example:
arrFib.filter(
(fib, index) => (index + 1) % 3 !== 0
)
I will definitely do that. I just wanted to make sure that such solution can be useful, that’s why I asked first.
Is it actually faster in Javascript? Since JS doesn’t have a proper integer type, that would be surprising to me.
This is a micro optimization I usually skip since 1) it’s less clear to most readers 2) compilers know how to optimize Mod 2 and 3) any language without an optimization pass probably won’t be used for a task where this difference is large enough to be appreciable.
function generateFibsArray(num) {
let fibsArray = [
[1, true],
[1, true]
];
let newFib = [
fibsArray[fibsArray.length - 1][0] + fibsArray[fibsArray.length - 2][0],
true
]
while (newFib[0] <= num) {
fibsArray.push(newFib);
newFib = [
fibsArray[fibsArray.length - 1][0] + fibsArray[fibsArray.length - 2][0],
true
]
}
return fibsArray;
}
function everyThirdIsFalse(arr) {
for (let i = 2; i < arr.length; i += 3) {
arr[i][1] = false;
}
return arr;
}
function sumFibs(num) {
let sumOddFibs = 0;
const Fibs = everyThirdIsFalse(generateFibsArray(num));
for (let fib of Fibs) {
if (fib[1]) {
sumOddFibs += fib[0];
}
}
return sumOddFibs;
}
console.log(sumFibs(1));//2
console.log(sumFibs(1000));//1785
console.log(sumFibs(4000000));//4613732
console.log(sumFibs(4));//5
console.log(sumFibs(75024));//60696
console.log(sumFibs(75025));//135721
To use property of Fibonacci numbers: every third number in the sequence is even.
To use boolean variables in order to avoid using division.
Use function generateFibsArray() to create 2D array. Every element: Fibonacci number <= num, and boolean value set to true
Flip boolean values to false for every third Fibonacci number, using function everyThirdIsFalse()
Perform calculations of result in the sumFibs() function
Your solution is relatively heavy, in my personal opinion. I think you can simplify matters if you avoid arrays - the second solution explicitly calls out the fact that dynamically creating arrays is relatively expensive. Here is my effort to simplify while still showing the same idea:
function sumFibs(num) {
let f0 = 0;
let f1 = 1;
let f2 = 1;
let sum = 0;
while (f1 <= num) {
// Update sum
// Note: every third Fibonacci number is even
// and the rest are odd
sum += f1;
if (f2 <= num) sum += f2;
// Compute next three Fibonacci numbers
[f0, f1] = [f1 + f2, f2 + (f1 + f2)];
f2 = f0 + f1;
}
return sum;
}
That said though, I think this would be a cool solution to add to the list of suggested solutions.
Yeah, I saw that. But my main intention was to exploit property of Fibs (every 3rd is even) somehow. In the process, I remembered that I also can avoid division here using booleans. To avoid arrays - wasn’t able to figure it out.
This your idea - to generate fibs in groups of three - I couldn’t figure it out on my own, that’s for sure!
If you have thoughts on how to make my solution clearer - please share!
I think this part is the hardest to parse and there are a few ways to write it. I’m not sure which is the clearest.
Well, this is solution for intermediate algo scripting section, right? I personally think, at this stage of curriculum students should be able to understand such lines of code. Maybe I am wrong though.
It still feels a bit like magic in the update part, but maybe this rearranging of comments helps?
function sumFibs(num) {
// Every third Fibbonaci number is even
// and the rest are odd
let f0 = 0;
let f1 = 1;
let f2 = 1;
// Generate triples until num is reached
let sum = 0;
while (f1 <= num) {
// Update sum
sum += f1;
if (f2 <= num) sum += f2;
// Compute next three Fibonacci numbers
[f0, f1] = [f1 + f2, f2 + (f1 + f2)];
f2 = f0 + f1;
}
return sum;
}
They say one learns best when one explains or teaches others. Maybe I am wrong though 
Regarding,
[f0, f1] = [f1 + f2, f2 + (f1 + f2)]; f2 = f0 + f1;
Could you please elaborate on what is actually happening here? I understand its leveraging destructuring assignment to some extent but that’s about it. If there is an explanation or documentation that explains what computation the syntax above achieves, it would be appreciated.
I mean any explanation/documentation beyond the destructuring assignment lessons within fCC.
That says
a) assign f0 = f1+f2 and b) f1 = f2+(f0+f1)
assign f2 = f0+f1
The destructuring is helpful because it let’s you do the first two assignments at the same time
This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.