Goldman Sachs Interview Question Software Engineer / Developers
0of 0 votesfind a^b using optimal algorithm.... [ no use of inbuilt functions?
Country: India
Interview Type: Phone Interview
Well your code doesn't work when the power is negative (i.e for negative b). You just have to change it a little bit. Add two lines to the code and everything will be ok.
if(b%2==0)
return(temp*temp);
else {
if(b > 1) {
return(temp*temp*a);
}
else {
return ((temp * temp)/a);
}
}
With those two lines it will work only when the power is negative even, not for odd.
What about this code to fix it?
#include <iostream>
double power(int a,int b)
{
std::cout<<a<<"^"<<b<<";";
double temp;
bool signedExp(b<0?true:false);
b=abs(b);
if(b==0)
{
return 1;
}
temp=power(a,b/2);
if (!signedExp)
{
if(b%2==0)
{
return(temp*temp);
}
else
{
return(temp*temp*a);
}
}
else
{
if(b%2==0)
{
return(1/(temp*temp));
}
else
{
return (1/(temp*temp*a));
}
}
}
int main()
{
int a(5),b(-5);
std::cout<<a<<"^"<<b<<"="<<power(a,b)<<std::endl;
}
lets take example
2^10 --> 2^9 * 2 ^1 --> 2^3 * 2^3 * 2^3 * 2^1
Algo:
1. Find nearest square root of power and remainder.
2. Calculate number ^ square root using multiplication and store it. Here 2^3 using multiplication.
3. Again find stored number ^ square root power. Here 2^3 is 8. So get 8 ^3 using multiplication that is 8 *8 *8.
4. Now multiply result with remainder of power. Here it is 512 * 2^1
HashMap<Integer, Long> hmap=new HashMap<Integer, Long>();
long power(int a, int b) {
if (b == 0)
return 1;
if (b == 1)
return a;
if(hmap.containsKey(b))
return hmap.get(b);
long p = power(a, b / 2) * power(a, b / 2);
if (b % 2 == 1)
p=p*a;
hmap.put(b, p);
return p;
}
uses DP also
Hmmm...well, I guess that makes sense. If you want to do it using pure recursion + memorization...still, check out some of the other solutions, they do it much more simply. You also could have just used long p = power (power(a, b / 2), 2), and there would have been no need for DP.
This solution has a bug. A small fix can resolve this.
Try calling the following two one after the other,
power(2,3);
power(3,3);
both will give you 8 as the answer.
@IC i get ur point
i am assuming u clear the map for every new a u get.
a small check can be done.
@eugene ur solution is very elegant .. :)
I just use maps for memoization in java
Is this practice wrong.
@salvo4u: It's not wrong; sometimes, I use it too. There are different ways to implement memorization and the best way depends on the structure of your problem. Sometimes an array is best; a map might be better when the array would be very sparse. A map is really more general. It's just that using memorization in this problem is not necessary.
Below code is writen in VS2008:
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
int power(int a, int b);
int _tmain(int argc, _TCHAR* argv[])
{
int exp = 0;
int pow = 0;
printf("Enter the base: ");
scanf("%d", &exp);
printf("\nEnter the power: ");
scanf("%d",&pow);
printf("2^3 : %d", power(exp,pow));
getch();
return 0;
}
int power(int a, int b){
return b == 0? 1: a*power(a,b-1);
}
//An O(log(n)) Non Recursive C# for unsigned ints.
//get the b th power of a
public static ulong Power(uint a, uint b)
{
ulong power = 1;
if (b > 0)
{
power = power * a;
if (b > 1)
{
uint largestBit = GetLargestBit(b);
uint position = 2;
uint rem = largestBit >> 1;
do
{
power = power * power;
if ((b & rem) > 0)
{
power = power * a;
}
rem = rem >> 1;
position = position << 1;
} while (b >= position);
}
}
return power;
}
//Get the max bit of a number
public static uint GetLargestBit(uint b)
{
uint largestBit = 1;
while (largestBit <= b)
{
largestBit = largestBit << 1;
}
largestBit = largestBit >> 1;
return largestBit;
}
#include<iostream.h>
#include<conio.h>
#define basevalue 5
#define powr 5
int power[powr];
void initilise() {
for(int i=0; i<powr; i++)
power[i] = 0;
}
int findPower(int value, int pow){
int num = pow;
power[0] = 1;
power[1] = value;
if(num == 0)
return power[num];
else if(pow == 1 || (power[num] != 0))
return power[num];
else {
if(pow % 2 == 0) {
if(power[num/2] != 0)
power[num] = power[num/2] * power[num/2];
else {
power[num/2] = findPower(value, num/2);
power[num] = power[num/2] * power[num/2];
}
}
else {
if(power[num/2] != 0 && power[num/2 + 1] != 0) {
power[num] = power[num/2] * power[num/2+1];
}
else {
power[num/2] = findPower(value, num/2);
power[num/2+1] = findPower(value, num/2+1);
power[num] = power[num/2] * power[num/2+1];
}
}
}
return power[pow];
}
int main()
{
int result;
initilise();
result = findPower(basevalue, powr);
cout<<"\n result = "<<result;
getch();
return 0;
}
Not optimal but workable solution :
class Power{
public int calculatePower(int x, int y)
{
int z =1;
for(int w=1;w<=y;w++)
{
z=z*w;
}
return z;
}}
public class SampleProgram extends Power{
public static void main(String[] args) {
Power p = new Power();
System.out.println("O/P Is:"+p.calculatePower(2,4));
}
}
#python
#converts to binary
def bin(b):
rem = [ ]
i = 0
while b !=0:
rem.append(i)
rem[i] = b % 2
b= b/2
i = i+1
rem.reverse()
return rem
#square and multiply
def power(a,b):
binary = bin(b)
ans = 1
for i in range(len(binary)):
ans = ans * ans
if binary[i] == 1:
ans = ans * a
return ans
power(2,3)
The first answer in this thread can be optimised further .
Here is the code
- Mahendra Pratap Singh on June 16, 2012 Edit | Flag Reply#include<iostream.h> int power(int a,int b) { int temp; if(b==0) return 1; temp=power(a,b/2); if(b%2==0) return(temp*temp); else return(temp*temp*a); } void main() { int a,b; cout<<"\nenter no.\n"; cin>>a; cout<<"\nEnter power\n"; cin>>b; cout<<a<<"^"<<b<<"="<<power(a,b)<<endl; }