# The Additive Chain

> Each value is the sum of the two before it - no calls to itself allowed.

Canonical URL: <https://datadriven.io/problems/the_additive_chain>

Domain: Python · Difficulty: easy · Seniority: L3 · Asked in: Antra

## Problem

Our retry scheduler spaces attempts by the Fibonacci sequence 0, 1, 1, 2, 3, 5, ..., and a job configured for `n` retries needs exactly the first `n` of those delays. Jobs with retries switched off still call it, with `n` of 0.

## Example

Input:

```
n = 7
```

Output:

```
[0,1,1,2,3,5,8]
```

## Worked solution and explanation

This is an off-by-one problem wearing a Fibonacci costume. Everyone knows each term is the sum of the previous two. What separates candidates is whether the list holds **exactly `n` values** at the bottom of the range. The reflex is to seed `[0, 1]` and loop `range(2, n)`. For `n` of 0 or 1 that loop never runs, and the seed leaks out unchanged. A job with retries switched off gets two delays, and a single-retry job also gets two.

### Walk the boundary first

#### Step 1: Settle `n` of 0 and 1 before seeding

Return `[]` when `n <= 0` and `[0]` when `n == 1`. These two inputs are exactly the ones the two-value seed cannot represent, so they have to exit before `[0, 1]` exists.

#### Step 2: Grow each term from the last two

With `[0, 1]` in hand, every new value is `sequence[i - 1] + sequence[i - 2]`. Starting at index 2 means the loop appends exactly `n - 2` values.

#### Step 3: Check the length against `n`

Trace the edges out loud. For `n` of 2, `range(2, 2)` is empty and you return the seed: two values, correct. For `n` of 7, five appends on top of two seeds give seven. Saying this trace is what convinces an interviewer the boundaries are handled on purpose.

**Guard the short cases, then build forward**

```python
def fibonacci_iterative(n):
    if n <= 0:
        return []
    if n == 1:
        return [0]
    sequence = [0, 1]
    for i in range(2, n):
        next_value = sequence[i - 1] + sequence[i - 2]
        sequence.append(next_value)
    return sequence
```

**Seed, then loop**

`sequence = [0, 1]` followed by `for i in range(2, n)`. This is right for `n` of 2 and up, but `n` of 0 and 1 both return `[0, 1]` because an empty loop never trims the seed.

**Guard, then seed**

Return `[]` for `n <= 0` and `[0]` for `n == 1` first. Only then seed `[0, 1]`, so the loop adds `n - 2` values and the length always equals `n`.

> **An empty loop does not mean an empty result**
>
> Candidates test `n` of 7, see the right list and stop. The bug only shows at 0 and 1, where nothing in the loop body ever executes and the hardcoded seed becomes the answer.

> **Recursion is the wrong instinct even when it is correct**
>
> Naive recursive Fibonacci recomputes subproblems and grows as roughly O(2^n). Even a memoized version deepens the call stack with `n` and hits the default limit near 1,000. The forward build has neither problem.

> **One pass, and the list is the only real cost**
>
> Time is O(n): one addition and one append per term. Space is O(n), because the caller asked for the whole list. Python integers never overflow, so even very long retry budgets stay exact.

## Common follow-up questions

- How would you return only the n-th delay without storing the full list? _(Tests holding two rolling variables for O(1) space.)_
- What changes if this ran in a language with 64-bit integers? _(The sequence passes the signed 64-bit maximum at the 93rd term, so it tests whether you know where overflow starts.)_
- Can you get the n-th value in O(log n) time? _(Tests matrix exponentiation: raising [[1,1],[1,0]] to a power by repeated squaring.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_additive_chain)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.