Coding

Sum of Fibonacci Numbers

Asked at

Amazon

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
    }
}

func sumFibonacci(n int) int64

Stuck? Show a way to structure it+

01State the identity sum through F(n) equals F(n plus 2) minus one.
02Compute Fibonacci values iteratively.
03Use a wide enough numeric type.
04Subtract one from F(n plus 2).

Reference answer

The useful identity is F(0) plus F(1) through F(n) equals F(n plus 2) minus 1. Prove it by induction: the base n = 0 gives 0 = F(2) minus 1, and adding F(n plus 1) transforms F(n plus 2) minus 1 into F(n plus 3) minus 1. Then iteratively compute Fibonacci numbers through n plus 2 using two rolling variables, avoiding an array. Return the final term minus one. Alternatively, keep a running sum in the same loop, but the identity makes the explanation sharper. This is O(n) time and O(1) extra space; for n at most 50, use a 64-bit integer because Fibonacci values quickly exceed 32-bit range. Clarify whether the stated n means inclusive F(n), as the examples do.

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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question