Discussion on Fibonacci GCD Challenge

8 years ago+ 1 comment

/* what's wrong with this code tle problem  */
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{
 if(a==0)
    return b;
  return gcd(b%a,a);
}
long long fib(long long c)
 {
  if(c<=1)
    return c;
  return (fib(c-1)+fib(c-2));
 }
int main()
{
  long long int n,ans,p,q;
  cin>>n;
   long long int a[n];
 for(int i=0;i<n;i++)
    cin>>a[i];
  ans=a[0];
  for(int i=1;i<n;i++)
  ans=gcd(ans,a[i]);
   p=fib(ans);
   cout<<p%1000000007<<endl;
}

4 years ago+ 0 comments

Working Python3 solution. Yours is "Naive Algo" which almost always gives TLE

P = 10 ** 9 + 7

from fractions import gcd
from functools import reduce, lru_cache

@lru_cache(maxsize = None)
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if (n & 1) == 1:
        return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
    else:
        return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P

n = int(input())
a = (int(input()) for _ in range(n))
g = reduce(gcd, a, 0)
print(fib(g))

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge