705. Three-Back Sequence
A bead artist threads a necklace by a strict rule. The first three beads are described by the numbers 0, 1 and 1 (positions 0, 1 and 2). Every later position gets a number equal to the sum of the three numbers just before it, so position 3 holds 2, position 4 holds 4, position 5 holds 7, and so on.
Given n, return the number at position n, counting positions from 0.
Compute it iteratively in time O(n) and extra space O(1), keeping only the three most recent numbers instead of the whole sequence.
Example 1
- Input:
- n = 12
- Output:
- 504
- Explanation:
Positions 0 to 12 hold 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, so position 12 holds 504.
Example 2
- Input:
- n = 19
- Output:
- 35890
- Explanation:
Continuing the same rule from position 12, the values grow to 35890 at position 19.
Constraints
0 ≤ n ≤ 37
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)