Print first n Fibonacci Numbers

Problem

Given a number N, find the first N Fibonacci numbers. The first two number of the series are 1 and 1.

Examples:

Example 1:

Input:
N = 5
Output: 1 1 2 3 5

Example 2:

Input:
N = 7
Output: 1 1 2 3 5 8 13

Your task:

Your task is to complete printFibb() which takes single argument N and returns a list of first N Fibonacci numbers.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(N)$

Note: This space is used to store and return the answer for printing purpose.

Constraints:

• $1<=N<=84$

Solution

Python

def printFibb(self,n):
    fib_list = []
    f1, f2 = 1, 1
    if n < 1:
        return fib_list
    fib_list.append(f1)
    for _ in range(1, n):
        fib_list.append(f2)
        next_fib = f1 + f2
        f1 = f2
        f2 = next_fib
    return fib_list

Java

public static long[] printFibb(int n) {
    long[] fibArray = new long[n];
    if (n < 1) {
        return fibArray; 
    }
    fibArray[0] = 1;
    if (n > 1) {
        fibArray[1] = 1;
    }
    for (int i = 2; i < n; i++) {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }
    return fibArray;
}

C++

public:
vector<long long> printFibb(int n) {
    vector<long long> fibVector(n); 
    if (n < 1) {
        return fibVector; 
    }
    fibVector[0] = 1;
    if (n > 1) {
        fibVector[1] = 1;
    }
    for (int i = 2; i < n; i++) {
        fibVector[i] = fibVector[i - 1] + fibVector[i - 2];
    }
    return fibVector;
}

C

int* printFibb(int n) {
    if (n < 1) {
        return NULL; 
    }
    int* fibArray = (int*) malloc(n * sizeof(int));
    if (fibArray == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1); 
    }
    int f1 = 0, f2 = 1;
    fibArray[0] = f1;
    if (n > 1) {
        fibArray[1] = f2;
    }
    for (int i = 2; i < n; i++) {
        int next_fib = f1 + f2;
        fibArray[i] = next_fib;
        f1 = f2;
        f2 = next_fib;
    }
    return fibArray;
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$