1836. Fibonacci Ladder
A plant grows by adding the last two heights, starting from heights 0 and 1, and the gardener records every height up to a limit. The sequence is F(0) = 0, F(1) = 1, and every later value is the sum of the two before it, so it begins 0, 1, 1, 2, 3, 5, 8.
Given the limit n, return every value F(0), F(1), F(2), ... in order, as long as the value is not larger than n. Both of the first two ones are listed, so the answer for n = 1 is [0, 1, 1] and the answer for n = 0 is [0]. The values grow quickly, so the answer is short even for the largest n. Aim for O(log n) time.
Example 1
- Input:
- n = 20
- Output:
- [0,1,1,2,3,5,8,13]
- Explanation:
The values up to 20 are 0, 1, 1, 2, 3, 5, 8 and 13.
Example 2
- Input:
- n = 0
- Output:
- [0]
- Explanation:
Only F(0) = 0 fits.
Example 3
- Input:
- n = 1
- Output:
- [0,1,1]
- Explanation:
F(0), F(1) and F(2) all equal 0 or 1, so both ones are listed.
Constraints
0 ≤ n ≤ 9 * 1015
the answer has at most 79 values
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(log n)
- Space
- O(log n)