Fibonacci Number
Calculate the nth Fibonacci number, where F(0) = 0, F(1) = 1, and each later value is the sum of the previous two.
Work through the cases
3 examplesInput notation
An integer n from 0 through 40.Expected result
F(n).Case 1
Input
8
Expected output
21
Case 2
Input
0
Expected output
0
Case 3
Input
1
Expected output
1
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Fibonacci obeys F_n = F_{n-1} + F_{n-2}. Naive recursion recomputes the same subproblems. Even though n ≤ 30, an iterative recurrence is enough. Roll two variables for consecutive terms and iterate n times. Time is linear and extra space is constant.
We define two variables a and b, initially a = 0 and b = 1.
Next, we perform n iterations. In each iteration, we update the values of a and b to b and a + b, respectively.
Finally, we return a.
The time complexity is O(n), where n is the given integer. The space complexity is O(1).
class Solution {
public int fib(int n) {
int a = 0, b = 1;
while (n-- > 0) {
int c = a + b;
a = b;
b = c;
}
return a;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.