BL
U

10. Generate First N Fibonacci Numbers

Easy

Problem Description

Given a positive integer NN, generate and print the first NN terms of the Fibonacci sequence. The sequence starts with F0=0F_0 = 0, F1=1F_1 = 1, and each subsequent term is Fi=Fi−1+Fi−2F_i = F_{i-1} + F_{i-2}.

Input Format

A single line containing an integer NN (1≤N≤501 \le N \le 50).

Output Format

Print the first NN Fibonacci numbers separated by a single space.

Example 1:
Input:
6
Output:
0 1 1 2 3 5
Explanation: The first 6 Fibonacci numbers are 0, 1, 1, 2, 3, 5.
Example 2:
Input:
1
Output:
0
Explanation: For N = 1, only the first term 0 is printed.
Example 3:
Input:
2
Output:
0 1
Explanation: For N = 2, the first two terms 0 and 1 are printed.
Constraints:
  • 1 <= N <= 50
  • Time complexity target: O(N)
  • Auxiliary space target: O(1)
Follow up:How would you compute F(N) modulo 10^9 + 7 for N = 10^18 using matrix exponentiation?
1,180 Online