CareerCup

double _power(double x, int y)
{
	if(y==0) return 1;

	double t = _power(x, y/2);
	t *= t;

	return t * ( (y%2)?x:1 );
}

double power(double x, int y)
{
	if(y<0) return - _power(x,-y);
	else return _power(x,y);
}

Look at this:

double power(double x, int y)
{
    if (y == 0)
        return 1.0;
    if (y == 1)
        return x;

    if (y < 0)
        return 1.0 / power(x, -y);

    if (y & 0x1 == 0) {
        double t = power(x, y/2);
        return t * t;
    }

    return x * power(x, y - 1);
}

double power_iterative(double x, int y)
{
    double result = 1.0;

    if (y == 0)
        return result;

    bool neg = false;

    if (y < 0) {
        neg = true;
        y = -y;
    }

    while (y) {
        if (y & 0x1)
            result *= x;
        x *= x;
        y >>= 1;
    }

    return neg ? 1.0 / result : result;
}

Improving on CPTjack's solution. Basically log2(b) will not always be an integer, hence the solution will have to multiply the base for any remainder. For example, if a=2 and b=6, log2(6) = 2.xx, hence the solution has to multiply the base for 6-4 = 2 more times.

double pow(double a, int b) {

        int exp=Math.abs(b),i;
        double base=a;

        if(exp==0) return 1.0;

        i=1;

        while((exp>=1) && (i< Math.abs(b)) ){
            if(exp > 1) {
                exp = exp/2;
                i= i*2;
                base = base*base;
            } else {
                i=i+1;
                base = base*a;
            }
        }

        if(b<0)
            return 1/base;
        else
            return base;

    }

public double pow(double a, int b) {

	while(b!=0)
	{
	int c = b%3;
	if(c==0)
	{
		a=a*a*a;
		b=b-3;
	}
	else if(c==1)
	{
		a=a*a*a*a;
		b=b-4;
	}
	else if(c==2)
	{
		a=a*a*a*a*a;
		b=b-5;
	}
	}
	
	return a;
	}

Is this O(log n) and how do you deduce that ?

en.wikipedia.org/wiki/Exponentiation_by_squaring

def double(a, b):
        print str(a) + str(" ") + str(b)
        a = int(a)
        b = int(b)
        if b == 0:
                return 1
        if b == 1:
                return a
        if b%2 == 0:
                return double(a*a, b/2)
        else:
                return a*double(a*a, (b-1)/2)

public static long power(int base, int raise) {
		long res = 1;
		for (int mask = 1; mask <= raise; base *= base, mask <<= 1) {
			if ((mask & raise) > 0) {
				res *= base;
			}
		}
		return res;
	}

public static float power(int x,int y){
		float temp;
		if(y==0)
			return 1;
		temp = power(x,y/2);
		if(y%2 ==0)
			return temp*temp;
		else
		{
			return x*temp*temp;
		}
		
	}

static double pow(double a, int b){
boolean isNegative = false;
if( b < 0 ){
b = b *-1 ;
isNegative = true;
}
if( b ==0 ) return 1;

double result = pow(a,b/2);
result = b%2 == 0? result*result : result*result*a;
return isNegative ? 1/result : result;
}


static double powNonReecursive(double a, int b){
boolean isNegative = false;
if( b < 0 ) {
b=b*-1;
isNegative = true;
}
double result = 1.0;
while( b != 0){
if(b%2 == 0){
a=a*a;
b= b/2;
}else{
result*=a;
b=b-1;
}
}
return isNegative ?1/result: result;
}

although its NP complete (en.wikipedia.org/wiki/Addition-chain_exponentiation)

here is the binary exponentiation version:

public static double pow(int a,int b){
                if(b==0 || a==1) return 1;
                if(b==1) return a;

                if(b<0)
                        return 1/pow(a,-b);

                return b % 2 == 0 ? pow(a,b/2) * pow(a,b/2) : a * pow(a,b-1);
        }

class Solution:
    # @param x, a float
    # @param n, a integer
    # @return a float
    def pow(self, x, n):
        if n == 0:
            return 1.0
        elif n == 1:
            return x
        elif n > 0:
            return pow(x, n // 2) * pow(x, n - n // 2)
        else:
            #n < 0:
            return 1.0 / pow(x, -n)

class Solution:
    # @param x, a float
    # @param n, a integer
    # @return a float
    def pow(self, x, n):
        if n == 0:
            return 1.0
        elif n == 1:
            return x
        elif n > 0:
            return pow(x, n // 2) * pow(x, n - n // 2)
        else:
            #n < 0:
            return 1.0 / pow(x, -n)

/** 
    * Returns a^b, as the standard mathematical exponentiation function 
    */ 
    public double pow(double a, int b) {
        double result = 1.0d;
        double square = a;
        while (b > 0) {
            if ((b & 1) == 1) {
                result *= square;
            }
            square = square * square;
            b = b >> 1;
        }
        return result;
    }

Negative b will require square root instead of square, but the idea is same.
I like bit operator over recursive call.

def custom_pow(a, b):
    if b < 0:
        return 1.0 / custom_pow(a, -b)
    exponent_to_value_map = collections.OrderedDict()
    current_exponent = 1
    current_value = a
    exponent_to_value_map[current_exponent] = current_value
    while 2 * current_exponent < b:
        current_exponent *= 2
        current_value = current_value * current_value
        exponent_to_value_map[current_exponent] = current_value
    residual_exponent = b - current_exponent
    while residual_exponent != 0:
        tmp_exp, tmp_val = 0, 1
        for exponent, value in exponent_to_value_map.iteritems():
            if exponent <= residual_exponent:
                tmp_exp = exponent
                tmp_val = value
            else:
                break
        residual_exponent -= tmp_exp
        current_value *= tmp_val
    return current_value

This will not work for (2,4) the expected output is 16 but your code will generate 32 because 2/2 is 1

public static int power(int a, int b) {
	    boolean isEven = true;
	    if(b == 0) return 1;
	    if(b == 1) return a;
	    else {
	          int result = a*a;
	          b = b-2;
	          while(b > 1) {
	                 result = result * result;
	                 int i = b%2;
	                 if(i > 0) {
	                	 isEven = false;
	                 }
	                 b = b/2;
	           }
	           if(b == 1 && !isEven)  return result * a;
		return result;
	     }    
	}

I had the same question asked....
I first gave a solution using DP (like fibonacci) with complexity N/2 = O(n)
Then I told him I can improve on this I gave another solution which was Log(n) (using memoization + recursion) something similar to top comment.

:( I guess I won't make it

int[] result = new int[b/2];

public double pow(double a, int b, int[] result) {
    if (b == 0) {
        return 1;
    }
    if (b == 1) {
        return a;
    }
    if (INTEGER.MAX_VALUE != result[b]) return result[b];
    if (b % 2 != 0) {
        result[b] = result[b - 1] * a;
        return result[b];
    }
    else {
        double _result = pow(a, b/2, result); 
        result[b] = _result * _result;
        return result[b];
    }

}

public class FindPowerOptimum {

	private double power(double a, int b) {
		// TODO Auto-generated method stub
		if (b == 0)
			return 1;
		if (a == 0)
			return 0;
		double output = 1;
		boolean isNegative = false;
		if (b < 0) {
			isNegative = true;
			b = -b;
		}
		output = findPowerR(a, b);
		if (isNegative) {
			output = 1 / output;
		}
		return output;
	}

	private double findPowerR(double a, int n) {
		// TODO Auto-generated method stub
		if (n == 0)
			return 1;
		if (n == 1)
			return a;
		double output = 1;
		output = findPowerR(a, n / 2);
		if (n % 2 == 0)
			return output * output;
		else
			return a * output * output;
	}

	public static void main(String[] args) {
		FindPowerOptimum fp = new FindPowerOptimum();
		System.out.println(fp.power(6, -6));
	}
}

int power(int a,int b)
{
 int x=a;
int ans=1;
while(b>0)
{
   if(b%2!=0)
   ans*=x;
   b>>=1;
   x*=x;
}
return ans;
}

private static double powerBinary(double a, int b){
		
		if(b == 0)
			return 1;
		if(b == 1)
			return a;
		else if(b%2 == 0)
			return powerBinary(a,b/2) * powerBinary(a,b/2);
		else
			return a* powerBinary(a,b/2) * powerBinary(a,b/2);
		
	}

b = 2^n1 + 2^n2 + ..... + 2^nx and we can easily get a, a^2, a^4, a^8.....

power(int a, int b) {
    if(b == 0) return 1;
    if(b == 1) return a;
    else {
          int result = a*a;
          b = b-2;
          while(b > 1) {
                 result = result * result;
                 b = b/2;
           }
           if(b == 1)  return result * a;
	return result;
     }    
}

function logPow(a,b) {
	if (b === 0) {
		return 1;		
	}
	
	if (b === 1) {
		return a;
	}
	
	if (b===2) {
		return a*a;
	}
		
	var count = Math.floor(b/2);
	var rest = b%2;
	var part1 = logPow(a,count);
	var partAns = part1 * part1;	
	
	if (rest === 1) {
	 	partAns *= a;
	}
	return partAns;
	
}

console.log(logPow(5,4));

You can do this on O(n) using bytes opertation:

int pow(int b, int exp)
{
int res = 0;

while(exp != 0)
{
if ((exp & 1) != 0)
{
res *= b;
}
exp >>= 1;
b *= b;
}
return res;
}

private double process(int a, int b) {
        boolean neg = false;
        if (a == 0) {
            return 0;
        } else if (b == 0) {
            return 1;
        }

        int result = a;
        if (b < 0) {
            b = -b;
            neg = true;
        }

        int pow = 1;
        while (b > 1 && (2 * pow) <= b) {
            int temp = result;
            result = temp * temp;
            pow *= 2;
        }

        int tempR = result;
        int tempP = pow;
        while (tempP > 0) {
            tempR /= 2;
            tempP /= 2;
            if ((pow + tempP) <= b) {
                pow += tempP;
                result *= tempR;
            }
        }

        return neg?1.0/result:result;
    }