Project Euler 2: Even Fibonacci numbers

This article shows the solution of Hackerrank challenges.

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 contain $T$ that denotes the number of test cases. This is followed by $T$ lines, containing an integer, $N$

Constraints

• $1 \leq T \leq 10^5$
• $10 \leq N \leq 4 \times 10^6$

Output Format

Print the required answer for each test case

Sample Input 0

1
2
3

2
10
100

Sample Output 0

1
2

10
44

Explaination 0

• For $N = 10$, we have ${2, 8}$, sum is $10$
• For $N = 100$, we have ${2, 8, 34}$, sum is $44$

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

void fibo_even(long long n){
    long long start = 2; //start of the fibonacci even number
    long long saved_start = 0;
    long long sum = 0;
    while (start < n){
        sum += start;
        long long temp = start;
        if (start * 4 + saved_start > n) break;
        start = start * 4 + saved_start;
        saved_start = temp;   
                
    }
    printf("%lld\n",sum);
}
int main(){
    int t; 
    scanf("%d",&t);
    for(int a0 = 0; a0 < t; a0++){
        long long n; 
        scanf("%lld",&n);
        fibo_even(n);
    }
    
    
    return 0;
}

Explaination

$1, 2, 3, 5, 8, 21, 34, 35, 89, 144, 233, 377, 610, …$

We have:

• $2 \times 4 = 8$
• $8 \times 4 + 2 = 34$
• $34 \times 4 + 8 = 144$
• $144 \times 4 + 34 = 610$

In general:

• $F(n) = 4F(n - 1) + F(n - 2)$