First n Fibonacci Numbers
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
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.
/*
* 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)
- How many earlier terms do you need to remember?