Fibonacci Sequence

Lab Java Beginner 10 points

Read n and print the first n Fibonacci numbers (starting 0 1) on one line.

Input

One integer 1–90.

Output

One line.

Example

Input

Output

0 1 1 2 3 5 8 13 21 34

Sample input available Sample output available

Editor

Java

Hints

Keep the last two numbers and move them forward each step.

Solution explanation

Two variables are enough - no array needed.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long a = 0, b = 1;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                sb.append(' ');
            }
            sb.append(a);
            long next = a + b;
            a = b;
            b = next;
        }
        System.out.println(sb);
    }
}

Output

Answer