Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

First Fibonacci With N Digits

Find the position of the first Fibonacci number that has n digits.

Bạn sẽ học được gì

  • Add two digit arrays
  • Generate Fibonacci terms without overflow
  • Stop at the first term that meets a condition

Đề bài

Xem bản dịch

The Fibonacci sequence starts F(1) = 1, F(2) = 1, and each next term is the sum of the two before it: 1, 1, 2, 3, 5, 8, 13, 21, ... Find where the sequence first reaches n decimal digits. The terms soon outgrow 64-bit integers, so add them as digit arrays if your language has no big integers.

Implement fibonacci_with_n_digits(n).

Input

n: The number of digits.

Output

Return the index i of the first term F(i) with at least n digits. For n = 1 the answer is 1.

Ràng buộc

1 ≤ n ≤ 1000

Ví dụ

Ví dụ 1
Đầu vào:
n = 2

Kết quả mong đợi:
expected = 7
Đầu vào:
long long n = 2;

Kết quả mong đợi:
long long expected = 7;
Đầu vào:
long n = 2;

Kết quả mong đợi:
long expected = 7;

Giải thích

F(6) = 8 has one digit and F(7) = 13 has two, so the answer is 7.

Ví dụ 2
Đầu vào:
n = 4

Kết quả mong đợi:
expected = 17
Đầu vào:
long long n = 4;

Kết quả mong đợi:
long long expected = 17;
Đầu vào:
long n = 4;

Kết quả mong đợi:
long expected = 17;

Giải thích

F(16) = 987 and F(17) = 1597, so the answer is 17.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Keep only the last two terms.

Gợi ý 2

Store each term as digits and add them with carries.

Gợi ý 3

Count the index as you go, starting from F(1) = 1.

Độ phức tạp mong đợi

O(n²) time, O(n) 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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.