DSA Tracker

Visualize

First n Fibonacci using DP

Rolling pair of terms, bounded by value rather than by count

time O(log n) termsspace O(1) beyond the output

Only the last two terms matter. Each new term is their sum, so the whole sequence can be walked with a pair of variables that shift right one place at a time. The twist compared with 'find the nth Fibonacci number' is the stopping rule: the loop is bounded by the VALUE of the next term against n, not by a count, so it computes one term too many on purpose and discards it. Because Fibonacci numbers only increase, the first term that overshoots n proves every later one does too — no need to look further.

Details

Animated on: n = 30 — print every Fibonacci number that is at most 30, starting from 0 and 1.

Problem:First n Fibonacci using DPEasy

Rolling pair of terms, bounded by value rather than by count

step 1 / 10

0
[0]
1
[1]

The two seeds 0 and 1 are given, not computed — every later term needs two predecessors to add, so the sequence cannot bootstrap itself. a and b always point at the last two terms; that pair is the entire state this loop carries.

  • a=0· arr[0] = 0
  • b=1· arr[1] = 1
Pseudocode
1FUNCTION fibonacciUpTo(n):
2  IF n < 1
3    RETURN [0]
4  series <- [0, 1]
5  WHILE TRUE
6    next <- series[LENGTH(series) - 1] + series[LENGTH(series) - 2]
7    IF next > n
8      BREAK
9    APPEND next TO series
10  RETURN series

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. The two seeds 0 and 1 are given, not computed — every later term needs two predecessors to add, so the sequence cannot bootstrap itself. a and b always point at the last two terms; that pair is the entire state this loop carries.
  2. Add the last two terms: 0 + 1 = 1. Nothing earlier in the series is read, which is why this stays a single pass over two variables instead of a lookup across everything printed so far.
  3. 0 + 1 = 1, still within the limit 30, so it joins the series and immediately becomes the new b while the old b (1) slides into a. The pair shifts right by one; the terms behind it are output only, never read again.
  4. 1 + 1 = 2, still within the limit 30, so it joins the series and immediately becomes the new b while the old b (1) slides into a. The pair shifts right by one; the terms behind it are output only, never read again.
  5. 1 + 2 = 3, still within the limit 30, so it joins the series and immediately becomes the new b while the old b (2) slides into a. The pair shifts right by one; the terms behind it are output only, never read again.
  6. 2 + 3 = 5, still within the limit 30, so it joins the series and immediately becomes the new b while the old b (3) slides into a. The pair shifts right by one; the terms behind it are output only, never read again.
  7. 3 + 5 = 8, still within the limit 30, so it joins the series and immediately becomes the new b while the old b (5) slides into a. The pair shifts right by one; the terms behind it are output only, never read again.
  8. 5 + 8 = 13, still within the limit 30, so it joins the series and immediately becomes the new b while the old b (8) slides into a. The pair shifts right by one; the terms behind it are output only, never read again.
  9. 8 + 13 = 21, still within the limit 30, so it joins the series and immediately becomes the new b while the old b (13) slides into a. The pair shifts right by one; the terms behind it are output only, never read again.
  10. 34 is past the limit 30, so the loop stops and 34 is never appended. Fibonacci terms only grow, so no later term could come back under 30 — 21 is the largest one that fits, and the 9 terms already collected are the whole answer.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve First n Fibonacci using DP in the editorAll Math problemsBack to roadmap