All challenges
Easy 0 solved 0% acceptance

First Fibonacci With N Digits

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

What you'll learn

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

Problem

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.

Constraints

1 ≤ n ≤ 1000

Examples

Example 1
Input:
n = 2

Expected output:
expected = 7
Input:
long long n = 2;

Expected output:
long long expected = 7;
Input:
long n = 2;

Expected output:
long expected = 7;

Explanation

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

Example 2
Input:
n = 4

Expected output:
expected = 17
Input:
long long n = 4;

Expected output:
long long expected = 17;
Input:
long n = 4;

Expected output:
long expected = 17;

Explanation

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

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Keep only the last two terms.

Hint 2

Store each term as digits and add them with carries.

Hint 3

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

Expected complexity

O(n²) time, O(n) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.