Given a number n, return an array containing the first n Fibonacci numbers.…
2024202520242025
Given a number n, return an array containing the first n Fibonacci numbers.
Note: The first two numbers of the series are 0 and 1.
Input format
A single line containing one integer n.
Output format
Print the first n Fibonacci numbers on one line, separated by single spaces.
Examples
Input | Output |
|---|---|
5 | 0 1 1 2 3 |
7 | 0 1 1 2 3 5 8 |
2 | 0 1 |
Constraints
1 <= n <= 30
Attempted by 1 students.
Show answer & explanation
Concept
The Fibonacci sequence starts with 0 and 1. Every later term is the sum of the two terms immediately before it.
To build the first n values, keep the sequence generated so far and append the sum of its last two values until its length reaches n.
Application
Read the single integer n from standard input.
If n = 1, the required sequence is 0 alone. If n is at least 2, start with 0 and 1.
While fewer than n terms have been produced, compute next = last value + second-last value and append next.
Stop at exactly n terms and print them on one line, separated by single spaces.
Cross-check
For n = 5 the sequence grows as 0, 1 then 0, 1, 1 then 0, 1, 1, 2 then 0, 1, 1, 2, 3. Each term after the first two equals the sum of the preceding two terms, so the printed line is 0 1 1 2 3.
Only the last two values are needed at any moment, so the loop runs in O(n) time and uses O(1) extra state beyond the printed output. The largest term reachable here is the 30th, 514229, which fits comfortably in a 32-bit integer.