Saturday 23 June 2012

Interviewstreet Fibonacci Factor - Amazon India Coding Challenge : Solution C++


Interviewstreet Amazon India Coding Challenge 

Fibonacci Factor Problem


Problem Statement

Given a number k, find the smallest Fibonacci number f that shares a common factor d( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them. 
Input: T test cases where each contains integer k in [2,1000000]
Output: two separate numbers, f and d, where f is the smallest fibonacci number and d is the smallest number other than 1 which divides both k and f.
 

Algorithm

1) For each fibonacci number f in [2,k] , find smallest common factor, findSCF(k,f) = d
2) if d > 1 print f and d
3) else continue until you get your f and d.
4) If fibonacci no not found in [2,k], keep looking for f in [k,infinity) until f%k == 0.

If you have a different approach in mind, please share it in the comments section.

Solution

/*All test cases have passed.*/

#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long int big;

big findSCF(big a, big b) {
  if(a%2==0 && b%2==0) return 2;
  for(big i = 3; i <= b; i+=2)
      if(a%i==0 && b%i==0) return i;
  return 1;
}

int main()
{

int k,t;
cin >> t;
while(t--)
{
cin >> k;
big f = 2, prev = 1, temp, d=1;
while(f<=k) {
  d=findSCF(k,f);
  if(d>1) break;
  temp=prev;
  prev=f;
  f+=temp;
}
if(d > 1)
cout << f << " " << d << endl;
else {
while(f%k!=0) {
   temp=prev;
   prev=f;
   f+=temp;
}
cout << f << " " << k << endl;
}
}
}

/* 
Since k can be 10^6, f can be as large as 10^18, so i have used unsigned long long int as variable type of 'f' 
*/



The next in the series is "Meeting Schedules - Amazon India Coding Challenge".


23 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. tarun I could not see your code properly, why dont you repost it??

    ReplyDelete
    Replies
    1. And now i found my mistake - i was not looking for f beyond k, all test cases have passed now.

      Delete
    2. // Previous code.

      #include[iostream]
      #include[algorithm]
      using namespace std;
      typedef unsigned long long int big;

      big findSCF(big a, big b) {
      if(a%2==0 && b%2==0) return 2;
      for(big i = 3; i <= b; i+=2)
      if(a%i==0 && b%i==0) return i;
      return 1;
      }

      int main()
      {

      int k,t;
      cin >> t;
      while(t--)
      {
      cin >> k;
      big f = 2, prev = 1, temp, d;
      while(f<=k) {
      d=findSCF(k,f);
      if(d>1) break;
      temp=prev;
      prev=f;
      f+=temp;
      }
      cout << f << " " << d << endl;
      }

      }

      Delete
    3. This comment has been removed by the author.

      Delete
  3. I am stuck on 9/10 and cant see what's wrong with my code. Your's works perfectly fine though. Can you help me find the error in mine?

    Code follows...

    #include<iostream>
    #include<cmath>
    using namespace std;
    int numT;
    unsigned long long int numK, fibNumber=2, fTemp1=1, fTemp2=1,k, con=10000000000000000000;
    int primeFactors[10];

    void generateNextFibonacci(){
    fTemp1=fTemp2;
    fTemp2=fibNumber;
    fibNumber=fTemp1+fTemp2;
    //cout<<':'<<fibNumber<<endl;
    }
    int main()
    {
    //cout<<"Hello World";
    cin>>numT;
    int numi,i,j;
    for(numi=0;numi<numT;numi++){
    j=0;
    fibNumber=2;
    fTemp1=fTemp2=1;
    cin>>numK;
    k=numK;
    for(i=2;i<=k;i++){
    if(k%i==0){
    k/=i;
    primeFactors[j++]=i;
    //cout<<primeFactors[j-1]<<",";
    while(k%i==0) k/=i;
    }
    }
    //for(i=0;primeFactors[i]!=0;i++) cout<<primeFactors[i]<<endl;
    j=0;
    while(fibNumber<=con){
    i=0;
    j=0;
    while(primeFactors[i]!=0){
    //cout<<fibNumber<<";"<<primeFactors[i]<<";"<<fibNumber%primeFactors[i]<<endl;
    if(fibNumber%primeFactors[i]==0){
    cout<<fibNumber<<" "<<primeFactors[i]<<endl;
    j=1;
    break;
    }
    i++;
    }
    if(j==1) break;
    generateNextFibonacci();
    }
    }
    }

    ReplyDelete
  4. Won't give correct result for t=361, just try.....
    Need to check this part of code

    ////////////
    while(f%k!=0) {
    temp=prev;
    prev=f;
    f+=temp;
    }
    ////////////
    you again need to check whether result would have SCF........

    ReplyDelete
    Replies
    1. right.. thanks gurman..

      when i was solving it under time-limit, i was more into passing all test cases on interview-street. so, i didn't see this case..

      Delete
  5. Hi guys, do you people get a call from amazon after solving all the questions...

    ReplyDelete
    Replies
    1. yes. I know few people in my circle who got shortlisted for onsite interviews.

      Delete
  6. How did you determine that f can be as large as 10^18?? it's not very clear to me

    ReplyDelete
    Replies
    1. It says under contraints that "The required fibonacci number is guranteed to be less than 10^18.", which is 19 decimal digits.

      Although with my working solution (that passed all the test cases), the F for K = 983 is 200 digits!

      Delete
  7. instead of going for the findSCF go for the gcd algorithm which is much better and thats what you want ...(a%k==0 and b%k==0)

    ReplyDelete
  8. This comment has been removed by the author.

    ReplyDelete
  9. Hey,I recently attempted to solve this question but only 4 of the test cases passed,can you please have a look at my code
    #include

    #include
    int gcd(int a,int b)
    {
    while(b!=0)
    {
    int m=a%b;
    a=b;
    b=m;
    }
    return a;
    }

    int fibo(int i)
    {
    int k;
    if(i==0||i==1)
    {return 1;}
    else
    {k=fibo(i-1)+fibo(i-2);
    return k;}
    }

    int main()
    {
    int test;
    scanf("%d",&test);
    int *input;
    input=(int *)malloc(sizeof(int)*test);
    for(int i=0;i<test;i++)
    {scanf("%d",&input[i]);}

    for(int i=0;i<test;i++)
    {
    int j=0;
    while(fibo(j)<=input[i])
    {
    if(gcd(fibo(j),input[i])!=1)
    {
    printf("%d %d\n",fibo(j),gcd(fibo(j),input[i]));
    break;
    }
    else
    j++;
    }
    }

    return 0;
    }

    ReplyDelete
  10. I just wonder what should be the output if the number input is a prime non fibonacci number? Ex : 7. Should it print "no fibonacci Factor found" ?

    ReplyDelete
  11. For this piece of code:
    while(f%k!=0) {
    temp=prev;
    prev=f;
    f+=temp;
    }
    Wouldn't it overflow? Or should we keep checking despite the overflow?
    try it for this number: 13081 which is a multiple of two primes(103 & 127). What should be the smallest fibonacci number which has a common factor with this number? Please make sure that the result IS a fibonacci number.

    ReplyDelete
  12. i have attempted this and cleared only 5. Every thing seems right. Please tell me where i have gone wrong.

    #include
    int gcd(int a,int b)
    {
    int c=b%a;
    if(c==0)
    return a;
    else
    return gcd(c,a);
    }

    int main()
    {
    unsigned long int a[150];
    int g=1,i,k[10],tc,tcn=0;
    a[0]=0;
    a[1]=1;
    for(i=2;i<50;i++)
    a[i]=a[i-1]+a[i-2];
    scanf("%d",&tc);
    for(i=0;i1)
    break;
    }
    printf("\n%d %d",a[i],g);
    tcn++;
    }
    }

    ReplyDelete
  13. This comment has been removed by the author.

    ReplyDelete
  14. Your code gives wrong answer at 13081. Code probably has issue in
    //
    while(f%k!=0) {
    temp=prev;
    prev=f;
    f+=temp;
    }
    //

    Answer is 1293530146158671551 103
    but it is giving 3937855734116042061 13081
    if 10381 can't be the smallest factor of the Fibonacci number and 10381 because of it is a factor so are 103 and 127.

    ReplyDelete
  15. i cant understand why it is going wrong pls explain

    #include

    void fib(unsigned long long int k)
    {
    unsigned long long int a,b=1,c=2,m,i;

    for(;;)
    {
    if(k%2==0)
    {
    printf("\nthe least common fibbonacci num having a common factor with %llu is:%llu,and the factor=%llu",k,c,c);
    return;
    }

    a=b;
    b=c;
    c=c+a;
    for(i=2;i<=c;i++)
    {
    if((k%i==0) && (c%i==0))
    {

    printf("\nthe least common fibbonacci num having a common factor with %llu is:%llu,and the factor=%llu",k,c,i);

    return;
    }
    }


    }
    }
    int main()
    {
    unsigned long long int k;
    int n,i;

    printf("\nenter the number of test cases:");
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
    printf("\nenter %d number:",i);
    scanf("%llu",&k);
    fib(k);
    }
    }

    ReplyDelete
  16. can you please check and inform where this code is consuming the most amount of time , my test cases show that i have run out of bound for three of the test cases, i crosse
    s the time limit....!!! please help ...

    CODE:
    #include
    #include
    #include

    using namespace std;
    long int testcase;

    long int min(long int val1,long int val2)
    {
    if(val1>testcase;
    long int f1[testcase],f[testcase],k[testcase],d[testcase];
    //input k values
    j=0;
    while(j>k[j];
    j++;
    }
    // cout<<"step 1 complete"< 1
    static long int prev[100];

    while (j<testcase)
    {
    prev[j]=1;
    f[j]=findfibonacci(prev[j],(long int)2,k[j]);
    j++;

    }

    /*
    // cout<<"step 2 comlete "<<endl;
    j=0;
    //find smallest no that divides both f and k
    while (j<testcase)
    {
    d[j]=smallestfactor(f[j],k[j]);
    j++;
    }
    // cout<<"step 3 complete"<<endl;
    j=0;
    while (j<testcase)
    {
    // f1[j]=f[j]-d[j];
    cout<<f[j]<<" "<<d[j]<<endl;
    j++;
    }

    */
    return 0;
    }

    ReplyDelete
  17. This comment has been removed by the author.

    ReplyDelete