1

I was trying Project Euler problem 25 on HackerRank.

I attempted a brute force method using Binet's Formula.

import math

for _ in range(int(input())):
    numLen = int(input())
    for x in range(1, 5000):
        fib = 1/pow(5,.5)*(pow(((1+pow(5,.5))/2),x) - pow(((1-pow(5,.5))/2),x))
        if(numLen == len(str(int(fib)))):
            print(x)
            break

Here 5000 is an arbitrary number based on the assumption input is not more than that and the problem is not here as its a runtime error which I'm think is because it's exceeding integer range(not sure).

It also calculates other test cases in less than 0.25 seconds.

I did some searching and found this.

but by that recurrence method:

import math

for _ in range(int(input())):
    a = 1
    b = 0
    n = int(input())
    term = 1
    while len(str(a)) != n:
        a, b = a+b, a
        term+=1
    print (term)

gives a timeout as it exceeds 10 seconds.

Can you please help me find a way to improve the first method and optimize the second method.

Note: I tried storing the pow() values in variables instead of recomputing and was of not much help.

Community
  • 1
  • 1
Ganesh Kathiresan
  • 2,068
  • 2
  • 22
  • 33

2 Answers2

1

Just use the second approach in your example but instead of computing the value separately for every line in input compute the values 1...5000 once and cache them:

res = [0]
a = 0
b = 1
term = 1

while len(res) <= 5000:
    a, b = b, a + b
    if len(str(a)) >= len(res):
        res.append(term)
    term += 1

print('\n'.join(str(res[int(input())]) for _ in range(int(input()))))

For input 2 3 4 it will produce the expected output 12 17. On my machine precomputing the values takes about 3 seconds.

niemmi
  • 17,113
  • 7
  • 35
  • 42
0

pow(x, y) is always slower than x**y and also pow() method cannot be used for long integers.

Try x**y , it would be bit faster

Mani
  • 933
  • 6
  • 15