Question

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

Answer 1

// Example: 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
fn fibonacci(n: usize) -> u64 {
    if n == 0 {
        return 0;
    }
    if n == 1 {
        return 1;
    }

    let mut prev: u64 = 0;
    let mut curr: u64 = 1;

    for _i in 2..=n {
        let next = prev + curr;
        prev = curr;
        curr = next;
    }

    curr
}

// Function to calculate sum of Fibonacci numbers from index L to R (inclusive)
fn sum_fibonacci_range(l: usize, r: usize) -> u64 {
    // 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)
    */

    fibonacci(r + 2) - fibonacci(l + 1)
}

fn main() {
    let left: usize = 2;
    let right: usize = 8;

    let result = sum_fibonacci_range(left, right);

    println!("Sum of Fibonacci numbers from index {} to {} = {}", left, right, result);
}



/*
run:

Sum of Fibonacci numbers from index 2 to 8 = 53

*/

 

70+ SQL courses for beginners and professionals