This kata I used a pattern common in fibonacci even numbers. In fibonacci series, every number is a factor of some Fibonacci number.
| i | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ... | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Fib(i) | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | ... | |
| F a c t o r s |
2=Fib(3) | ✔️ | ❌ | ❌ | ✔️ | ❌ | ❌ | ✔️ | ❌ | ❌ | ✔️ | Every 3rd Fib number |
| 3=Fib(4) | ❌ | ✔️ | ❌ | ❌ | ❌ | ✔️ | ❌ | ❌ | ❌ | ✔️ | Every 4th Fib number | |
| 5=Fib(5) | ❌ | ❌ | ✔️ | ❌ | ❌ | ❌ | ❌ | ✔️ | ❌ | ❌ | Every 5th Fib number | |
| 8=Fib(6) | ❌ | ❌ | ❌ | ✔️ | ❌ | ❌ | ❌ | ❌ | ❌ | ✔️ | Every 6th Fib number | |
| F(k) | ... | F(all multiples of k) | ||||||||||
As you can see every third number is a multiple of two. So the approach we are going to use is to find fibonacci of multiples of three.
/** num is the number we are going to use to find
n-th fibonacci. this time we are going to be
finding fibonacci of multiples of 3. sum holds
the sum of all even numbers. prev is holding
the value from fibonacci calculation
**/
function solution(max) {
let num = 3;
let sum = 0;
let prev = fibo(num);
while(prev < max) {
sum += prev;
num += 3;
prev = fibo(num);
}
return sum;
}
/* Here I used memoized fibonacci algorithm to reduce time
and improve efficiency of our algorithm */
function fibo(n, memo={}) {
if (n < 2) return n;
if(memo[n]) return memo[n];
memo[n] = fibo(n - 1, memo) + fibo(n - 2, memo);
return memo[n];
}
Top comments (0)