Understanding the Problem

The Fibonacci sequence begins with 0 and 1, and every term after that is the sum of the two terms immediately before it. So the third term is 0 + 1 = 1, the fourth is 1 + 1 = 2, the fifth is 1 + 2 = 3, and the sequence continues 5, 8, 13, 21, and so on. The task is to produce the first n of these numbers as an array, in order.

Here n is the number of terms to generate, not the value of the last term. For n = 5, the first five terms are 0, 1, 1, 2, and 3, so the answer is [0, 1, 1, 2, 3].

Two inputs at the low end need attention. When n is 1, only the first term exists, so the answer is [0] rather than both seed values. When n is 0, there are no terms to produce, so the answer is an empty array. The same holds for any negative n, since you cannot generate a negative number of terms.

Key Constraints:

n can be 0 → There are no terms to generate, so the result is an empty array. The loop must run zero times and return an empty result rather than the seed values.
n can be 1 → Only the first term, 0, belongs in the output. The result is [0], not [0, 1], so the second seed value must not be emitted on its own.
The terms grow quickly → Fibonacci numbers roughly double each step, so the value at term 47 already exceeds the range of a signed 32-bit integer. Keeping n within the stated bound avoids overflow in a fixed-width type.

Approach 1: Two-Variable Iteration

Intuition

Each term depends only on the two terms before it, so two variables are enough: one for the previous term and one for the current term.

Hold prev = 0 and curr = 1, the first two terms. On each step, append prev to the result, then advance the pair so that the new prev is the old curr and the new curr is the sum prev + curr. Appending prev first makes the seeds come out in order: the first append emits 0, the second emits 1, and from there each appended value is the sum computed one step earlier. Appending before advancing means n = 1 emits only the 0 and stops, with no special handling.

Algorithm

Create an empty list to hold the result.
Set prev = 0 and curr = 1.
Repeat n times: append prev to the list, then set prev, curr = curr, prev + curr.
Return the list as an array.

Example Walkthrough

Input:

Start with prev = 0 and curr = 1, and run the step five times. First, append prev = 0, then advance to prev = 1, curr = 1. Second, append prev = 1, then advance to prev = 1, curr = 2. Third, append prev = 1, then advance to prev = 2, curr = 3. Fourth, append prev = 2, then advance to prev = 3, curr = 5. Fifth, append prev = 3, then advance to prev = 5, curr = 8. The loop has run five times, and the collected result is [0, 1, 1, 2, 3]. The values 5 and 8 are computed but never appended, since the loop stopped after five terms.

result

Code

Complexity Analysis

Time Complexity: O(n). The loop runs exactly n times, producing one term per iteration with constant work each step.
Space Complexity: O(n) for the result array, which holds all n terms. Beyond the output, only the two rolling variables are used, so the extra space is O(1).

Print Fibonacci Up to N Terms