Labels

Project Euler #25: N-digit Fibonacci number

Question
The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

Answer : 4782

Hacker Rank Problem

Solution


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.*;

public class Solution {

    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;
    }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) 
    {
        Scanner s=new Scanner(System.in);
        int t=s.nextInt();
        LinkedList love=new LinkedList();
        for(int bjp=0;bjp<t;bjp++)
        {
            int n=s.nextInt();
            int i=0,g=1;
            while(g!=n)
            {
                g=Solution.fact(i);
                i++;
            }
            System.out.println(i-1);
        }
        
    }
    static int fact(int n)
    {
        double d = (n * Math.log10(1.6180339887498948)) - 
                   ((Math.log10(5)) / 2); 
      
        return (int)Math.ceil(d); 
    }
}
Labels:

Comments

Post a Comment

Popular Posts