## 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) = d2) 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;

}

}

}

#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".

This comment has been removed by the author.

ReplyDeletetarun I could not see your code properly, why dont you repost it??

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

Delete// Previous code.

Delete#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;

}

}

This comment has been removed by the author.

DeleteI 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?

ReplyDeleteCode 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();

}

}

}

Won't give correct result for t=361, just try.....

ReplyDeleteNeed 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........

right.. thanks gurman..

Deletewhen 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..

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

ReplyDeleteyes. I know few people in my circle who got shortlisted for onsite interviews.

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

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

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

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)

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteHey,I recently attempted to solve this question but only 4 of the test cases passed,can you please have a look at my code

ReplyDelete#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;

}

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" ?

ReplyDeleteFor this piece of code:

ReplyDeletewhile(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.

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

ReplyDelete#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++;

}

}

This comment has been removed by the author.

ReplyDeleteYour code gives wrong answer at 13081. Code probably has issue in

ReplyDelete//

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.

i cant understand why it is going wrong pls explain

ReplyDelete#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);

}

}

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

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

}

This comment has been removed by the author.

ReplyDelete