EULER CODE - 2

QUESTION:-

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and, 2 the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …………

By considering the terms in the Fibonacci sequence whose values do not exceed N, find the sum of the even-valued terms. 

Input Format 

First-line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Constraints

• 1 ≤ T ≤ 10⁵
• 10 ≤ N ≤ 10¹⁷

Output Format

Print the required answer for each test case.

Sample Input

2

10

100

Sample Output

10

44

Explanation

For N = 10, we have {2,8} , sum is 10 .

For N=100, we have {2,8,34} , sum is 44 .

Ans:-

A very simple relation can make you able to solve this problem. You can see the next even number E(n) is always related to two previous even numbers E(n-1) and E(n-2) in the following manner.

                             E(n) = 4*E(n-1)+E(n-2)

Using this simple relation it is now pretty easy to code the problem and pass the time and space complexity easily.

C++ CODE:

#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long int t,n,f=0;

    cin >> t;

    while(t--)

    {

        long long int sum=0;

        cin >> n;

        long long int f2 = 0,f1 = 2;

        while(f1<n)

        {

            sum+=f1;

            f = 4*f1+f2;

            f2 = f1;

            f1 = f;

        }

        cout << sum << endl;

    }

    return 0;

}

PYTHON CODE:

t = int(input())
f = 0
for i in range(t):
    sum = 0
    n = int(input())
    f2=0
    f1=2
    while(f1<n):
        sum+=f1
        f = 4*f1 + f2
        f2 = f1
        f1 = f
    print(sum)

Hope that helps. Keep Coding :)