To write down code for x^n in O(logn) time.

Question

HC · Accepted Answer

slightly optimized one:
template
T power(T base, unsigned int n) {
	if (0 == n) return 1;
	if (1 == n) return base;
	T tmp = power(base, n / 2);
	tmp *= tmp;
	if (0 == n % 2) {
		return tmp;
	}
	return base * tmp;
}

Scott Liu · Answer

linear:
A^8 = A*A*A*A*A*A*A*A
log:
A^8 = (A^4)*(A^4)
A^4 = (A^2)*(A^2)
A^2 = A*A

websqueeze · Answer

def powlogn(x, n):
    if x == 0:
        return 1
    elif x == 1:
        return x
    elif n%2:
        return x * powlogn(x*x, (n-1)/2)
    else:
        return powlogn(x*x, n/2)

\/. · Answer

Use Intel compiler, it does it automatically.

Easy Question · Answer

A^(2k)=A^k*A^k
A^(2k+1)=(A^k)*(A^k)*A

Chauhan · Answer

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

Time Complexity of optimized solution: O(logn)

Citadel

Citadel interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches