CareerCup

Also assume that a and b are always integers

See geeksforgeeks.org/forum/topic/amazon-interview-question-for-software-engineerdeveloper-2-5-years-about-algorithms-3

int pow(int a, int b)
{
int num = a;
int result = 0;

for(int i = 0; i < (b - 1); ++i) {
for(int j = 0; j < a; ++j) {
result += num;
}
num = result;
}
return result;
}

Even I have the same solution. But this will work only for positive powers. How about when b is negative??

My solution ::

public class a_power_b_using_add_subtract {
public static void main(String args[]) {
int a = 10, b = 3;
System.out.println(pow(a, b));
}

public static int pow(int a, int b) {

if (b == 0)
return 1;
else if (b == 1)
return a;
else {
int result = a;
for (int i = b; i > 1; i--) {
int temp = result;
for (int j = a; j > 1; j--) {
result = result + temp;
}
}
return result;

}
}
}

how will any of the solution mentioned above take care of negative powers?
for example pow (4, -2) ?

pow ( a, b)
break b in power of 2s. b= 2^k1 + 2^k2 + ...
now for each break up make left shift or right bit shift of a depending on b is +ve or -ve.
then add the each term by no of times equal to next term.

correction to dchitkara to work with -ve also
1.Convert -ve base to +ve base.

int pow(int a, int b)
{
int num,end;
int result = 0;
if(a<0)
num=a*(-1);
end=num;
for(int i = 0; i < (b - 1); ++i) {
for(int j = 0; j < end; ++j) {
result += num;
}
num = result;
}
int sign=1;
if(a<0 && b%2)
sign=-1;
return result*sign;
}

This is my solution for positive integers

int pow(int a, int b)
{
int num = a;
int result = 0;

for(int i = 0; i < (b - 1); ++i) {
for(int j = 0; j < a; ++j) {
result += num;
}
num = result;
} 
return result; 
}

Sorry, I pasted something else previously....this is the right code

#include <iostream>
using namespace std;

int pow(int a, int b)
{int ans, i, j, temp;
ans = a;
temp = a;
 if(b==0)
	return(1);
for(i=0; i<b-1; i++)
	{
	 for(j=0; j<a-1; j++)
		ans=temp+ans;
	 temp=ans;
	}
 return(ans);
}


int main()
{int a, b;
 cin>> a >> b;
 cout << pow(a,b);
}

MS IDC makes fool of people.
People have to come to office on weekends due to workload and do night outs, no work life balance. They pay 10-20% more make people labour.

Do take the feedback from employees before joining MS.

And work is junk, all junk wor from Redmond is transferred to IDC. Ask any team, whether they design, implement products or just do porting or maintenance or make tools.

pow(n,a) = pow(n-1,a)*a
You can use this to build a recursive program to calculate the power
pow(n, val)
{
if(n==1) return val;
int ret = pow(n-1, val);
for(int i = 0 ;i < val;i++)
{
ret+=ret;
}
return ret;
}

int mul( int a , int b )
{

int x = 0 , y = a ;


while ( b )
{
if ( b&1 )
x = x + y ;

y = y + y ;

b = b >> 1 ;
}

return x;
}


int pow( int a , int b )
{
int x = 1 , y = a ;


while ( b )
{
if ( b&1 )
x = mul(x,y) ;

y = mul(y,y) ;

b = b >> 1 ;
}

return x;
}




****************************
This will compute a^b in O((log(b))^2).
mul(a,b) calculates a*b in O(log(b)) and pow(a,b) also similarly calculates a^b.