I've just copied my code from C++ and changed it to Java (used long instead of long long int) and it works like a charm!

every variable and function use long long and you could get it.

use unsigned long long int sum=0; long int f0 = 2; long int f1 = 8; long int f2

same dude, I solved using matrix exponentiation but still got WA

Change the parameter to long n, and its all right

You just gotta use long long and you'll get it. Don't know why all these people are downvoting you instead of just pointing it out.

did not get you...

if you check the series 0, 1, 2, 3, 5, 8 which is the fibinoacci series every third term is even and the next even term sequence can be caluclated using 4 * (8) + 2 which is 4*(n-3) + (n- 6)

wow, the solution is so neat

Actually it does. One can skip few steps Using this formula one will get only the even fibinoacci numbers. Traditional algo will be :

f1=1;

f2=2;

f=0;

while(f1 less than n)

{

if(f%2==0) sum+=f;

f=f1+f2;

f2=f1;

f1=f;

}

print -> sum

However you can skip the step of verifing odd-even. Also you are skiping 2 odd number and directly getting only the even numbers.

f1=2;

f2=0;

f=0;

while(f1 less than n) {

sum+=f1;

f=4*f1+f2;

f2=f1;

f1=f;

}

print -> sum

PS-Sorry for bad english

Well, test case #3 completed in less than half the time using this technique for me. Using Python 3.

Instead of recursion I used this formula and it should cut down complexity quite a bit, but I still get two timeouts, so not sure what my algo is doing to be so slow.

Binet's Formula

the observation reduce computation by 66%, as two loop cycles each round are skipped including the computation

Same :/

same -_-

The problem here is that your fiboAdd has too many unnecessary calculations:

1. The most serious offender is the fiboEven function. Let's say you calculate fiboEven(10), you recursively call fiboEven(9) and fiboEven(8) but the whole recursive subtree rooted at fiboEven(8) is contained in fiboEven(9). You need memoization. This is the same reasoning as the standard reasoning for why it's good to have memoization for recursive fibonacci series calculation. You don't want a recursion tree (with branching factor a=2) if you can effectively get a recursion list (with branching factor a=1).

2. The successive fiboEven(i) calls in addFibo(N) are also redundant with the recursion tree for i+1 going through recursion tree for i, even though you just went through it in the previous outer fiboEven call. You need to keep track of the previously calculated fiboEven(i-1) to quickly calculate fiboEven(i).

3. Also, for each i you call fiboEven(i) in fiboAdd twice: inside if statement and on the next line. So, you can cut you workload in half by saving the result in a variable and reusing.

Personally, I think (bottom-up) iterative approach is a better fit here because you don't need any memoization you just keep the previous fiboEven number, the current fiboEven number and the current sum in memory and that's it.

Try to do precalculation and store it in list. You will get it

if(fiboEven(i)<=N) so if it is == N then it will still add fiboEven making it larger than N.

Thank you so much. I finally passed.

well this won't give any timeouts but one test case is failing , i think it's because of inaccuracy we get in golden ratio while calculating it for very large term for e.g. the following code will generate 27th term as 37889062373143904 instead of 37889062373143906. rectify it and you will get the correct code :)

int main(){
    int t; 
    scanf("%d",&t);
    for(int a0 = 0; a0 < t; a0++){
        long n, sum = 0; 
        scanf("%ld",&n);
        long curr_num = 2;
        while(curr_num<=n){
            sum += curr_num;
            curr_num = (long)floor((pow(((1 + pow(5 , 0.5)) / 2),3) * curr_num + 0.5));
            //sum += curr_num;
        }
        printf("%ld \n", sum);
    }
    return 0;
}

sorry for late advice - store the first fibbonachi numbers in memory and go thrue tests $-)

import functools
@functools.lru_cache(maxsize=None)
def fib(n):
    if n<=2:
        return 1
    else:
        return fib(n-1) + fib(n-2)



n = int(input().strip())
s=0
for i in range(3,n,3):
    _ = fib(i)
    if _<=n:
        s+=_
    else:
        break
        
print(_)

all works on slow but wise Python

Fibonacci_index

It's not perfect. When k = 12, n = 7. However, the n-th term for F is 13. We can check agaisnt this quickly with the same formula going forwards and backwards ONCE. instead of over a loop like everyone has been doing.

I should mention the relationship I gues. F_0 = 0, E = F_{3n}

I should mention, all this is useless past a certain point on a computer since percision is slowly lost. However, NASA has a great article on how accurate pi needs to be.