Question

How to calculate the sum of all Fibonacci numbers between two left and right indices in C++

Answer 1

#include <iostream>

// Eample: left = 2, right = 8;
// Explanation: F(2) + F(3) + F(4) + F(5) + F(6) + F(7) + F(8) = 1 + 2 + 3 + 5 + 8 + 13 + 21 = 53

// Function to compute nth Fibonacci number
std::pair<long long, long long> getNthFibonacciNumber(long long n) {
    if (n == 0) return {0, 1};
    
    auto p = getNthFibonacciNumber(n >> 1);
    
    long long a = p.first;  // F(k)
    long long b = p.second; // F(k+1)
    
    long long c = a * (2 * b - a);
    long long d = a * a + b * b;
    
    if (n & 1) return {d, c + d};
    
    return {c, d};
}

long long fibonacci(long long n) {
    return getNthFibonacciNumber(n).first;
}

long long sumFibonacciRange(int left, int right) {
    // Formula: Sum(F_left ... F_right) = F_(right+2) - F_(left+1)
    return fibonacci(right + 2) - fibonacci(left + 1);
}

int main() {
    int left = 2, right = 8;

    std::cout << "Sum of Fibonacci numbers from index " 
              << left << " to " << right << " = "
              << sumFibonacciRange(left, right) << std::endl;
}



/*
run:

Sum of Fibonacci numbers from index 2 to 8 = 53

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>

// Eample: left = 2, right = 8;
// Explanation: F(2) + F(3) + F(4) + F(5) + F(6) + F(7) + F(8) = 1 + 2 + 3 + 5 + 8 + 13 + 21 = 53

// Function to compute Fibonacci numbers up to n 
unsigned long long fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    unsigned long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        unsigned long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    
    return curr;
}

// Function to calculate sum of Fibonacci numbers from index L to R (inclusive)
unsigned long long sumFibonacciRange(int L, int R) {
    // If the range is invalid (e.g., L > R), return 0
    if (L > R) return 0;

    /*
      Mathematical identity:
      Sum(F_L + F_(L+1) + ... + F_R) = F_(R+2) - F_(L+1)

      Explanation:
      - The sum of the first n Fibonacci numbers is F_(n+2) - 1.
      - So, the sum from F_L to F_R can be derived by subtracting:
          (sum of first R terms) - (sum of first (L-1) terms)
        = (F_(R+2) - 1) - (F_(L+1) - 1)
        = F_(R+2) - F_(L+1)
    */

    return fibonacci(R + 2) - fibonacci(L + 1);
}


int main() {
    int left = 2, right = 8;

    unsigned long long result = sumFibonacciRange(left, right);
    
    std::cout << "Sum of Fibonacci numbers from index " 
              << left << " to " << right << " = "
              << sumFibonacciRange(left, right) << std::endl;
}



/*
run:
 
Sum of Fibonacci numbers from index 2 to 8 is: 53
 
*/

 

70+ SQL courses for beginners and professionals