Project Euler #2: Even Fibonacci numbers

  • + 2 comments

    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

    • + 0 comments

      This does not change the time complexity from O(n) however.

      Orignal time is something like O(3n) -> O(n)

      New time complexity is something like O(2n/3) -> O(n)

    • + 2 comments
      #include <map>
      #include <set>
      #include <list>
      #include <cmath>
      #include <ctime>
      #include <deque>
      #include <queue>
      #include <stack>
      #include <string>
      #include <bitset>
      #include <cstdio>
      #include <limits>
      #include <vector>
      #include <climits>
      #include <cstring>
      #include <cstdlib>
      #include <fstream>
      #include <numeric>
      #include <sstream>
      #include <iostream>
      #include <algorithm>
      #include <unordered_map>
      
      using namespace std;
      
      
      int main(){
          int t;
          cin >> t;
          for(int a0 = 0; a0 < t; a0++){
              long n;
              cin >> n;
              long long int f1 = 1,f2 = 2,f = 0, sum = 0;
              while(f1 < n)
              {
                  if(f1 % 2 == 0)
                  {
                      sum += f1;
                  }
                  f = f1 + f2;
                  f1 = f2;
                  f2 = f;
                  //cout << f1 << endl;
              }
              cout << sum << endl;
          }   return 0;
      }
      
      • + 1 comment

        LOL bro, why you've added those headers? ☻

        • + 1 comment

          is it working for testcase 2 and 3?? i guess not.

          • + 0 comments

            that code is working..do in c++ editor

      • + 0 comments

        wrong output