Problem

Write an iterator that yields all Fibonacci numbers up to a given upper bound top. Use it to:

  • get the highest Fibonacci number less than 1000 (expected 987), and
  • find whether there is a Fibonacci number ≤ 1000 that is a multiple of 12 (expected 144).

The iterator version mirrors the behaviour of a generator; both yield the same sequence. Generators are usually more concise in Python, but iterators demonstrate how the protocol works under the hood.

Examples

Example 1

1
2

Input: top = 1000
Output: highest = 987, first_fib_multiple_of_12 = 144
Similar Problems

Solution

Method 1 — Iterator class

Intuition

Maintain the two most recent Fibonacci numbers, a and b. Each step returns a and updates (a, b) = (b, a+b). Stop when a > top.

Approach

  • Initialize a = 0, b = 1, and store top.
  • On each next()/__next__() call:
    • If a > top raise StopIteration (or return a sentinel for languages without exceptions).
    • Store result = a.
    • Update a, b = b, a + b.
    • Return result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class FibonacciIterator {
 public:
  FibonacciIterator(long long top) : top_(top), a_(0), b_(1) {}
  bool hasNext() const { return a_ <= top_; }
  long long next() {
    long long r = a_;
    auto nxt = a_ + b_;
    a_ = b_;
    b_ = nxt;
    return r;
  }
 private:
  long long top_, a_, b_;
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

package main

type FibonacciIterator struct{ top, a, b int }
func NewFibonacciIterator(top int) *FibonacciIterator { return &FibonacciIterator{top:top, a:0, b:1} }
func (it *FibonacciIterator) Next() (int, bool) {
  if it.a > it.top { return 0, false }
  r := it.a
  it.a, it.b = it.b, it.a+it.b
  return r, true
}
1
2
3
4
5
6
7

class FibonacciIterator implements java.util.Iterator<Long> {
  private final long top;
  private long a = 0, b = 1;
  FibonacciIterator(long top) { this.top = top; }
  public boolean hasNext() { return a <= top; }
  public Long next() { long r = a; long nxt = a + b; a = b; b = nxt; return r; }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class FibonacciIterator(private val top: Long) : Iterator<Long> {
  private var a = 0L
  private var b = 1L
  override fun hasNext() = a <= top
  override fun next(): Long {
    val r = a
    val nxt = a + b
    a = b; b = nxt
    return r
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class FibonacciIterator:
  def __init__(self, top: int):
    self.top = top
  def __iter__(self):
    self.a = 0
    self.b = 1
    return self
  def __next__(self) -> int:
    if self.a > self.top:
      raise StopIteration
    result = self.a
    self.a, self.b = self.b, self.a + self.b
    return result
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

pub struct FibonacciIterator { top: u128, a: u128, b: u128 }
impl FibonacciIterator {
  pub fn new(top: u128) -> Self { FibonacciIterator { top, a:0, b:1 } }
}
impl Iterator for FibonacciIterator {
  type Item = u128;
  fn next(&mut self) -> Option<u128> {
    if self.a > self.top { return None }
    let r = self.a;
    let nxt = self.a + self.b;
    self.a = self.b; self.b = nxt;
    Some(r)
  }
}
1
2
3
4
5
6
7
8

class FibonacciIterator {
  top: number; a = 0; b = 1;
  constructor(top: number) { this.top = top }
  next(): { value: number, done: boolean } {
    if (this.a > this.top) return { value: 0, done: true }
    const r = this.a; [this.a, this.b] = [this.b, this.a + this.b]; return { value: r, done: false }
  }
}

Complexity

  • ⏰ Time complexity: O(k) to generate k Fibonacci numbers (each step constant time).
  • 🧺 Space complexity: O(1) extra space (just a few integers to track state).

Method 2 — Generator / producer

Intuition

Generators produce the same sequence with less boilerplate. In Python use yield. In Go use a goroutine + channel. The generator approach is concise and clear.

Approach

  • Start with a = 0, b = 1 and while a <= top:
    • yield a
    • update a, b = b, a + b

Code

1
2
3
4
5

// adapter using FibonacciIterator
void generateFib(long long top, const std::function<void(long long)>& cb) {
  FibonacciIterator it(top);
  while (it.hasNext()) { cb(it.next()); }
}
1
2
3
4
5
6

// channel-based generator implemented via FibonacciIterator
func FibGenerator(top int) <-chan int {
  ch := make(chan int)
  go func(){ it := NewFibonacciIterator(top); for { v, ok := it.Next(); if !ok { break }; ch <- v }; close(ch) }()
  return ch
}
1
2
3
4
5
6
7
8
9

// stream adapter using FibonacciIterator
import java.util.stream.Stream;
import java.util.Spliterators;
import java.util.stream.StreamSupport;

public static Stream<Long> fibStream(long top) {
  FibonacciIterator it = new FibonacciIterator(top);
  return StreamSupport.stream(Spliterators.spliteratorUnknownSize(it, 0), false).takeWhile(v -> v <= top);
}
1
2
3
4

fun fibSequence(top: Long) = sequence {
  val it = FibonacciIterator(top)
  while (it.hasNext()) { yield(it.next()) }
}
1
2
3

def fib_generator(top: int):
  for v in FibonacciIterator(top):
    yield v
1
2
3
4

// adapter returning the existing FibonacciIterator
fn fib_generator(top: u128) -> impl Iterator<Item = u128> {
  FibonacciIterator::new(top)
}
1
2
3
4
5
6

// generator implemented using FibonacciIterator
function* fibGenerator(top: number) {
  const it = new FibonacciIterator(top);
  let res = it.next();
  while (!res.done) { yield res.value; res = it.next() }
}

Complexity

  • ⏰ Time complexity: O(k) to produce k numbers.
  • 🧺 Space complexity: O(1) per generator instance (plus any channel/iterator buffers in some languages).

Notes

  • Use generators for concise code in languages that support them (Python, Kotlin, TypeScript). Use iterator classes when you need explicit control over state or to interoperate with APIs expecting an iterator object.
  • Fibonacci numbers grow exponentially; the k-th Fibonacci is ≈ phi^k / sqrt(5). The number of Fibonacci numbers ≤ top is O(log top).