Đề bài
Begin the sequence with 1 and 2. Each following term is the sum of the previous two. Include only even-valued terms no greater than limit, then add them.
Implement even_fibonacci_sum(limit).
Input
limit: The largest term value that may be included.
Output
Return the sum, or 0 if there are no eligible terms.
Ràng buộc
0 ≤ limit ≤ 10¹⁵. The result fits a signed 64-bit integer.
Ví dụ
Đầu vào:
limit = 50
Kết quả mong đợi:
expected = 44Đầu vào:
long long limit = 50;
Kết quả mong đợi:
long long expected = 44;Đầu vào:
long limit = 50;
Kết quả mong đợi:
long expected = 44;Giải thích
The even terms are 2, 8, and 34. Their sum is 44.
Đầu vào:
limit = 1
Kết quả mong đợi:
expected = 0Đầu vào:
long long limit = 1;
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long limit = 1;
Kết quả mong đợi:
long expected = 0;Giải thích
The first even term is 2, which exceeds the limit.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
You only need the even Fibonacci terms, not the entire sequence.
Gợi ý 2
Generate the sequence until the next term exceeds the limit and add qualifying terms.
Gợi ý 3
Watch the boundary when the limit itself is a Fibonacci term.
Độ phức tạp mong đợi
O(log limit) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.