Qualcomm Interview Question Software Engineer / Developers
int power(int m,int n)
{
if(n==1)
return m;
return power(m,n/2)*power(m,n/2);
}
This is O(log N) and divide and conquer. The one given by Jiez is O(log n) and transform and conquer.
Man, the question itself has problem: there is always an O(N) effeciency for Power(M, N), since you actually don't save any '*' operation during divide and conquer, you have to have N-1 times of '*' operations. The reason why you don't save is operation '*' is 2 operand operations and it is transmisive. Consider m^8, you will divide eventually to (m*m)*(m*m) * (m*m)*(m*m), if you take all the parenthisis out, then you just have plain m*m*m*m*m*m*m*m, so there is no need to divide at all!
Exactly!
And the second question would be more interesting if the interviewer asks "find out if a given number N to be a power of M?" So you can extend first give the answer for "if N is a power of 2", which is easier, then just replace the 2 with M
If we try to solve the complexity of the problem, this is what we get..
let power(m,n) be T(n) and T(1) = m
T(n) = T(n/2) * T(n/2);
= T(n/4) * T(n/4) * T(n/4) * T(n/4)
= T(n/8) * T(n/8) * T(n/8) * T(n/8) * T(n/8) * T(n/8) * T(n/8) * T(n/8)..
= ...
= .. .
and so on till
T(n/n) + T(n/n) + .... n times ... + T(n/n)
which is equal to
m * m * m * m..... n number of times.
hence this is not in log(N)
It should be O(LogN) because it divides the number with N recursively
bool power(int M, int N)
{
int result = N/M;
if(result > M) return power(M,result);
else
if(result%M == 0)
return 1;
else
return 0;
- Taesung October 31, 2009}