← All questions
Coding

Sum of Fibonacci Numbers

Asked atAmazon
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The problem

Given an integer n, return the sum of the first n Fibonacci numbers, starting with 0 and 1.

The Fibonacci sequence is defined as: F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2) for n ≥ 2

You are required to return the sum F(0) + F(1) + ... + F(n).

Input: n = 3 **Output: **4 Explanation: F(0) + F(1) + F(2) + F(3) = 0 + 1 + 1 + 2 = 4

Input: n = 5 Output: 12 **Explanation: **0 + 1 + 1 + 2 + 3 + 5 = 12

**Input: **4

  • 0 <= n <= 50

cpp

class Solution {
public:
    long long sumFibonacci(int n) {
        // Your code goes here
    }
};

java

class Solution {
    public long sumFibonacci(int n) {
        //Your code goes here
    }
}

python

class Solution:
    def sumFibonacci(self, n: int) -> int:
        # Your code goes here

javascript

class Solution {
    sumFibonacci(n) {
        // Your code goes here
    }
}

csharp

class Solution {
    public long SumFibonacci(int n) {
        // Your code goes here
    }
}

go

func sumFibonacci(n int) int64
Stuck? Show a way to structure it+
  1. 01State the identity sum through F(n) equals F(n plus 2) minus one.
  2. 02Compute Fibonacci values iteratively.
  3. 03Use a wide enough numeric type.
  4. 04Subtract one from F(n plus 2).

Reference answer

Then expect these follow-ups

  • How would fast doubling reduce runtime to O(log n)?

    Tests: complexity analysis

  • Can you derive a similar identity for even-indexed terms?

    Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with EnzoSign up free

Next question