First n Fibonacci Numbers

easy Programming Basics

Problem

Read n. Print the first n Fibonacci numbers on one line, separated by a space. The series starts 0, 1, 1, 2, 3, 5, ...

Constraints

  • 1 <= n <= 40

Examples

Input

7

Output

0 1 1 2 3 5 8

Solutions

Best approachTime O(n)Space O(n)

Only the last two terms are needed, so two variables are enough. The terms grow quickly; with a 32-bit int the 48th term overflows, so this problem limits n.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process a number.
 * Input   : One integer n.
 * Output  : The Fibonacci terms.
 * Approach: Two running variables.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int[] solve(long n) {
        // Step 1: Every term is the sum of the two terms before. Keep the last two terms in "previous" and "current".
        // For n up to 40 every term fits in an int.
        int previous = 0;
        int current = 1;
        int[] terms = new int[(int) n];

        // Step 2: Save the current term, then move both variables one step forward.
        for (int i = 0; i < terms.length; i++) {
            terms[i] = previous;
            int next = previous + current;
            previous = current;
            current = next;
        }
        return terms;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(Arrays.stream(solve(n)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}
Hints (1)
  1. How many earlier terms do you need to remember?