Sum of the Two Before

Easy

A sequence of numbers is built like this: position 0 holds 0, position 1 holds 1, and every later number is the sum of the two numbers right before it. Given index, return the number at that position of the sequence (positions are 0-based).

Example 1

index=6 → 8

The sequence starts 0, 1, 1, 2, 3, 5, 8. Position 6 holds 8 = 3 + 5.

Example 2

index=1 → 1

The second starting number is given directly: it is 1.

Example 3

index=0 → 0

Constraints

0 ≤ index ≤ 40

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Recursion Memoization Math Dynamic Programming

Similar problems

Every Bracketing Result Medium Paving a Garden Path Easy Sum of the Last Three Easy How Many Ones Are Written Hard Shared Pool Race to a Goal Medium

Input

index=6

Expected

Run checks the first 3 tests in your browser. Submit checks all 20 tests on the server, hidden ones included.