euler-002.cpp

// ////////////////////////////////////////////////////////
// # Title
// Even Fibonacci numbers
//
// # URL
// https://projecteuler.net/problem=2
//
// # Problem
// 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 four million,
// find the sum of the even-valued terms.
//
// # Solved by
// Lyndsey Gu
// February 2023
//
// # Input format
// First line contains T that denotes the number of test cases. This is followed 
// by T lines, each containing an integer N.
// 
// # Algorithm
// As explained in the problem statement, you can compute all Fibonacci numbers in an iterative way:
// `F_i=F_{i-2}+F_{i-1}`
//
// My variables ''a'' and ''b'' stand for `F_{i-2}` and `F_{i-1}` whereas ''next'' is `F_i`
// After each iteration, ''next=a+b'' and then ''a'' becomes ''b'' and ''b'' becomes ''next''.
//
// A number is even if there is no remainder when divided by 2.
// In most programming languages it's written as ''variable % 2 == 0''
//
// Internally, your compiler might translate this to the more efficient ''(variable & 1) == 0''
//
// # Note
// ''unsigned long long'' is required to pass all Hackerrank tests.

#include <iostream>

using namespace std;

int main() {
    unsigned int tests;
    cin >> tests;

    while (tests--) {
        unsigned long long last;
        cin >> last;

        unsigned long long sum = 0;

        // first Fibonacci numbers
        unsigned long long a = 1;
        unsigned long long b = 2;

        // until we reach the limit
        while (b <= last) {
            // even ?
            if (b % 2 == 0) {
                sum += b;
            }

            // next Fibonacci number
            auto next = a + b;
            a = b;
            b = next;
        }

        cout << sum << endl;
    }

    return 0;
}