We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #25: N-digit Fibonacci number
  4. Discussions

Project Euler #25: N-digit Fibonacci number

Sort by

recency

|

87 Discussions

|

  • rohit_w_kumar
     + 0 comments

    Java Soln

    import java.util.*;

    public class Solution { public static int minFibonacciWithNDigits(int digits) { if (digits == 1) return 1; // F1 = 1 has 1 digit

        double phi = (1 + Math.sqrt(5)) / 2;
    double log10_phi = Math.log10(phi);
    double log10_sqrt5 = 0.5 * Math.log10(5);

    // Rearranged Binet's formula to solve for n
    int n = (int)Math.ceil((digits - 1 + log10_sqrt5) / log10_phi);

    return n;
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while (t-- > 0) {
        int n = sc.nextInt();
        System.out.println(minFibonacciWithNDigits(n));
    }
}

    }

  • tjmfollosco
     + 0 comments

    I used Binet's Formula. Only got 3/4 test case.

    public static void getFibs(int digit)
    {
        if(digit == 1) { Console.WriteLine(1); }
        else
        {
            double phi = 1.61803;
            double approx = Math.Pow(10,digit-1);
            double sqrtFive = Math.Sqrt(5);
            double ans = 0;
            int nth = 0;
            for(int i = 1; ans < approx; i++)
            {
                ans = Math.Pow(phi,i) / sqrtFive;
                nth = i;
            }
            Console.WriteLine(nth);
        }
        
    }

  • akshaymoolath
     + 0 comments
    #python
a=1
b=1
c=10
term=[0, 0]
s=0
for x in range(3, 25000):
    s=a+b
    a=b
    b=s
    if s/c>=1:
        c*=10
        term.append(x)
t=int(input())
for x in range(t):
    n=int(input())
    print(term[n])

  • shubham_dasarwar
     + 0 comments
    import sys
sys.set_int_max_str_digits(5000)

def fibo_length():
    a, b = 0, 1
    memo = {}
    length = 1
    index = 1
    while length <= 5000:
        if len(str(b))==length:
            memo[length] = index
            length+=1
        a, b = b, a + b
        index+=1
    return memo

# memoized fibonacci element's length with thier index
memo = fibo_length()

t = int(input())
for _ in range(t):
    n = int(input())
    print(memo.get(n))

  • Venkateshgurram5
     + 0 comments
    import sys
sys.set_int_max_str_digits(5000)
d={1:1,}
i,j=2,3
first,second=1,1
while i<=5000:
    first,second=second,first+second
    if len(str(second))==i and i not in d:
        d[i]=j
        i+=1
    j+=1
     
t=int(input().strip())
for _ in range(t):
    n=int(input().strip())
    print(d[n])