Microsoft Interview Question Developer Program Engineers
Country: India
Interview Type: Written Test
Like the solution. FYI here the matrix M is [2 2; 1 0] and initial condition I is [3;1]
No, the matrix will be [1 1; 1 0] only. Check it for small cases.
If you raise this matrix to the power of n then the result would be [F(n+1) F(n); F(n) F(n-1)]. Since it is easy to just return the (0,0) element of the matrix, I returned F[0][0] which is actually the "(n+1)th" fabonacci number.
The problem is "like" Fibonacci but not "Fibonacci" because f(n)=2f(n-1) + 2f(n-2). [1 1; 1 0] is for f(n)=f(n-1) + f(n-2)
@axecapone: while reading this solution, same thing strike me,plz tell me if f(1)=x and f(2)=y then by what value matrices m[][] and f[][] will be initialize. i.e. what will be initial condition, and how you are finding it. this solution for fibonacci is new for me, i like it..
I didn't understand the solution....can anyone pleas explain..
applying this code for n=3, i m getting 3 but it should be 8...how?
@axecapone: how r u getting initial condition I [3;1] and whts it's requirement in this problem??
Awaiting for reply...
@axacapone...
frnd we can left shift the result of fib..function to get our desired result..
but still its not solved in O(log n ) complexity
it takes O(n) time
There can be O(1) solution.
This is basically a recurrence relation.
I have solved it & got the solution:
f(n)=a1*(1+3^0.5)^n + a2*(1-3^0.5)^n
where a1= 0.3943375673
a2= 0.1056624327
put the value of n & get output.
@Manan, if you are not able to understand the logic, you can fire questions regarding. I don't think that downvoting will make you understand the logic or you are downvoting only for fun rather than understanding the logic?
If you cant explain the logic, There is no point putting your answer here.... downvoted for no explanation
ok, let me explain:
f(n)=2*(f(n-1)+f(n-2))
The recurrence relation would look like : r^2=2*(r+1)
i.e. r^2-2*r-2
r=1+3^0.5 & 1-3^0.5
say r1 & r2
Now, f(n) = a1(r1)^n + a2(r2)^n----------------------original
There are two unknowns a1 & a2.
We have,
f(1)=a1(r1) + a2(r2) = 1----------------------equation 1
f(2)=a1(r1)^2 + a2(r2)^2= 3-------------------equation 2
Solve the two equations, you will get the values of a1 & a2.
Put the values of a1,a2,r1,r2 in the original equation, you will get the result.
Hope its clear.
Good solution shondik. Upvoted!
@Manan, Read about recurrence relation equation on Wiki. Explaining it here is beyond the scope of this problem
@shondik
Dont you think doing (1+3^0.5)^n for large n can lead to precision errors and can sway a lot from the actual answer which would be an interger as the equation func(n) = 2*(func(n-1)+func(n-2)) does not contain any floating point value. This can be solved in O(logn) as proposed by Boson and without any floating point operations.
At first glance of the problem, I also come up with this solution. But calculating a1*(1+3^0.5)^n will also need at least log(n) time.
Not sure. This is what I could see towards the end.
"What remains is how to compute TN-1 efficiently. The most popular method is to use exponentiation by squaring method that works in O(log N) time, with this recurrence:
A^{p} = A \text{, if } p = 1,
A^{p} = A .A^{p-1} \text{, if } p \text{ is odd,}
A^{p} = X^{2} \text{, where } X = A^{p/2}\text{, otherwise.}
Multiplying two matrices takes O(K3) time using standard method, so the overall time complexity to solve a linear recurrence is O(K3 log N)."
Power of DP O(log n)
Matrix findNthPower( Matrix M , power n )
{
if( n == 1 ) return M;
Matrix R = findNthPower ( M , n/2 );
R = RxR; // matrix multiplication
if( n%2 == 1 ) R = RxM; // matrix multiplication
return R;
}
Well what you are asking is to actually find the nth fibonacci number in O(log n) time which is possible by using the dynamic programming approach. After that you can just multiply it by 2.
The matrix { {1,1,}, {1,0} } when raised to the power of n will give the (n+1)th fibonacci number at its (0,0) position.
Here is the working code to find the nth fibonacci number in O(log n) time -
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if( n%2 != 0 )
multiply(F, M);
}
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
int main()
{
int n = 9;
printf("%d", fib(9));
getchar();
return 0;
}
Well what you are asking is to actually find the nth fibonacci number in O(log n) time which is possible by using the dynamic programming approach.
The matrix { {1,1,}, {1,0} } when raised to the power of n will give the (n+1)th fibonacci number at its (0,0) position.
Here is the working code to find the nth fibonacci number in O(log n) time -
- Anonymous July 06, 2012void multiply(int F[2][2], int M[2][2]) { int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } void power(int F[2][2], int n) { if( n == 0 || n == 1) return; int M[2][2] = {{1,1},{1,0}}; power(F, n/2); multiply(F, F); if( n%2 != 0 ) multiply(F, M); } int fib(int n) { int F[2][2] = {{1,1},{1,0}}; if(n == 0) return 0; power(F, n-1); return F[0][0]; } int main() { int n = 9; printf("%d", fib(9)); getchar(); return 0; }