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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #25: N-digit Fibonacci number
  4. Discussions

Project Euler #25: N-digit Fibonacci number

Contest ends in
Problem
Submissions
Leaderboard
Discussions

Sort 83 Discussions, By:

recency

Please Login in order to post a comment

  • Venkateshgurram5
    3 weeks ago+ 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])
    
    0|
    Permalink
  • cafelatte
    1 month ago+ 0 comments

    Could make up my mind whether to use a formula or run through all Fibo numbers up to 5000 digits, so I did both:

    import sys
    sys.set_int_max_str_digits(5010)
    from decimal import *
    import random
    
    def fib():
        a, b = 1, 1
        while ...:
            yield a
            a, b = b, a+b
    
    def main():
        # preload n[digits]
        n = [0]
        lastd = 0
        for i, f in enumerate(fib(), 1):
            d = len(str(f))
            if d > lastd:
                lastd = d
                n.append(i)
                if d == 5000: break
                # if d == 50: break
        # do queries
        r5 = Decimal(5**.5)
        lphi = Decimal((1+r5)/2).ln()
        
        for _ in range(int(input())):
            q = int(input())
            n_formula = (r5 * 10**(q-1)).ln() / lphi
            print( random.choice([
                n_formula.to_integral_value(rounding = ROUND_CEILING),
                n[q]
            ]))
    
    main()
            
    
    0|
    Permalink
  • hoangziet22
    1 month ago+ 0 comments

    **Can someone explain to me why this code is runtime error **

    #List a save the result
    a = [0, 1, 7, 12, 17, 21, 26, 31, 36, 40, 45, 50, 55, 60, 64, 69, 74, 79, 84, 88, 93, 98, 103, 
     107, 112, 117, 122, 127, 131, 136, 141, 146, 151, 155, 160, 165, 170, 174, 179, 184, 189,
     194, 198, 203, 208, 213, 217, 222, 227, 232, 237, 241, 246, 251, 256, 261, 265, 270, 275,
     280, 284, 289, 294, 299, 304, 308, 313, 318, 323, 328, 332, 337, 342, 347, 351, 356, 361,
     366, 371, 375, 380, 385, 390, 395, 399, 404, 409, 414, 418, 423, 428, 433, 438, 442, 447,
     452, 457, 462, 466, 471]
     
    t = int(input())
    for i in range(t):
        n = int(input())
    
    0|
    Permalink
  • ketan_patel25
    2 months ago+ 0 comments

    Java code runing all test

    import java.io.*;
    import java.util.*;
    import java.math.*;
    
    public class Solution {
    
        // public static void main(String[] args) {
        //     /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        // }
        
    //public static void main(String[] args) {
            /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
            // Scanner sc = new Scanner(System.in);
            // int n=sc.nextInt();
            // String str1;
    
    
            // for(int i=0;i<n;i++){
            //     int val=sc.nextInt();
            //     int cnt=0;    
            //     BigInteger a = BigInteger.valueOf(0); 
            //     BigInteger b = BigInteger.valueOf(1); 
            //     BigInteger c = BigInteger.valueOf(1); 
    
            // for (BigInteger bi = BigInteger.valueOf(1000000000000L);
            //     bi.compareTo(BigInteger.ZERO) > 0;
            //     bi = bi.add(BigInteger.ONE)){
                
            //     c =  a.add(b); 
            //     a = b; 
            //     b = c;
                
            //     str1 = a.toString();  
            //     cnt++;
                
            //     if(val==str1.length())
            //     break;  
            // } 
            // System.out.println(cnt);
    
            // }
            
    public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int t = in.nextInt();
            while (t-- > 0) {
                int a0 = in.nextInt();
                if (lastBitNum <= a0) {
                    calc(a0);
                }
                System.out.println(result[a0]);
            }
            in.close();
        }
    
        static int LENGTH = 10000;
    
        static int DIGIT_NUMBER = 5001;
    
        static int[][] a = new int[2][DIGIT_NUMBER];
    
        static int[] result = new int[DIGIT_NUMBER];// store the result
    
        static int lastBitNum = 1;// digit N
    
        static int lastArrayIndex = 2;// which term
    
        /**
         * initial
         */
        static {
            a[0][0] = 1;
            a[1][0] = 1;
        }
    
        static void calc(int i) {
    //        System.out.println(LocalDateTime.now());
            while (lastBitNum <= i) {
                lastArrayIndex = find(lastBitNum, lastArrayIndex);
    //            System.out.println("lastBitNum : " + lastBitNum + " index : " + lastArrayIndex);
                lastBitNum++;
            }
    //        System.out.println(LocalDateTime.now());
        }
    
        /**
         * 
         * @param lastBitNum
         * @param lastArrayIndex
         * @return
         */
        private static int find(int lastBitNum, int lastArrayIndex) {
            int[] tmp = new int[DIGIT_NUMBER];
            while (true) {
                tmp = nextFibonacciNum(a[0], a[1]);
                a[0] = a[1];
                a[1] = tmp;
                int bitNum = calcBit(tmp);
                lastArrayIndex++;
                if (bitNum == lastBitNum) {
                    result[lastBitNum] = lastArrayIndex;
                    return lastArrayIndex;
                }
            }
        }
    
        static int calcBit(int[] a) {
            int index = 0;
            for (int i = a.length - 1; i >= 0; i--) {
                if (a[i] > 0) {
                    return i + 1;
                }
            }
            return index;
        }
    
        private static int[] nextFibonacciNum(int[] a, int[] b) {
            int[] c = new int[a.length];
            int carry = 0;
            for (int i = 0; i < DIGIT_NUMBER; i++) {
                int result = (a[i] + b[i] + carry);
                int remainder = result % 10;
                c[i] = remainder;
                carry = result / 10;
            }
            return c;
        }
    
        
    }
    
    0|
    Permalink
  • vidush_rk11
    6 months ago+ 0 comments
    import sys
    sys.set_int_max_str_digits(6000)
    
    li=[1,1]
    answers=[0,1,]
    x=2
    max_len=1
    
    # I simultaneously calculate the fibonacci numbers and set an answers list corresponding to the nth term which has digits >= that indice of the list
    while max_len<5000:
        x+=1
        new_number=li[-2]+li[-1]
        length=len(str(new_number))
        li.append(new_number)
        if length>max_len:
            answers+=[x]*(length-max_len)
            max_len=length
            
    for _ in range(int(input())):
        n=int(input())
        print(answers[n])
    
    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy