Đề bài
Bắt đầu dãy số với 1 và 2. Mỗi số tiếp theo là tổng của hai số liền trước. Chỉ lấy các số có giá trị chẵn và không lớn hơn limit, sau đó cộng chúng lại.
Cài đặt hàm even_fibonacci_sum(limit).
Đầu vào
limit: Giá trị lớn nhất của một số trong dãy có thể được lấy.
Đầu ra
Trả về tổng các số hợp lệ, hoặc 0 nếu không có số nào thỏa mãn.
Ràng buộc
0 ≤ limit ≤ 10¹⁵. Kết quả nằm trong phạm vi của số nguyên có dấu 64-bit.
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
Các số chẵn là 2, 8 và 34. Tổng của chúng là 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
Số chẵn đầu tiên là 2, nhưng đã vượt quá giới hạn.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chỉ cần các số Fibonacci chẵn, không cần cả dãy.
Gợi ý 2
Sinh dãy cho đến khi số tiếp theo vượt quá giới hạn rồi cộng các số thỏa điều kiện.
Gợi ý 3
Chú ý trường hợp giới hạn chính nó là một số Fibonacci.
Độ phức tạp mong đợi
thời gian O(log limit), bộ nhớ phụ O(1)
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.