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.
importjava.io.*;importjava.util.*;importjava.math.*;publicclassSolution{// 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);// }publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intt=in.nextInt();while(t-->0){inta0=in.nextInt();if(lastBitNum<=a0){calc(a0);}System.out.println(result[a0]);}in.close();}staticintLENGTH=10000;staticintDIGIT_NUMBER=5001;staticint[][]a=newint[2][DIGIT_NUMBER];staticint[]result=newint[DIGIT_NUMBER];// store the resultstaticintlastBitNum=1;// digit NstaticintlastArrayIndex=2;// which term/** * initial */static{a[0][0]=1;a[1][0]=1;}staticvoidcalc(inti){// 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 */privatestaticintfind(intlastBitNum,intlastArrayIndex){int[]tmp=newint[DIGIT_NUMBER];while(true){tmp=nextFibonacciNum(a[0],a[1]);a[0]=a[1];a[1]=tmp;intbitNum=calcBit(tmp);lastArrayIndex++;if(bitNum==lastBitNum){result[lastBitNum]=lastArrayIndex;returnlastArrayIndex;}}}staticintcalcBit(int[]a){intindex=0;for(inti=a.length-1;i>=0;i--){if(a[i]>0){returni+1;}}returnindex;}privatestaticint[]nextFibonacciNum(int[]a,int[]b){int[]c=newint[a.length];intcarry=0;for(inti=0;i<DIGIT_NUMBER;i++){intresult=(a[i]+b[i]+carry);intremainder=result%10;c[i]=remainder;carry=result/10;}returnc;}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #25: N-digit Fibonacci number
You are viewing a single comment's thread. Return to all comments →
Java code runing all test