CareerCup

Hi,

Just thought to summarize the possible motivation behind this question.
- Check to handle negative number.
- Check for minimum iteration
- Check for recursion concepts.
- Check for bitwise operators
- Check for O(Log N) solution by n/2 recursive solution
- Check for basic ideology of multiply, which is addition.
- Check for overflow condition handling. ( For C#, One can also read about checked keyword)

There are multiple variants of this question depending on the exact problem statement from interviewer. One can easily fit subset of above check's into the problem and come up with a robust source code.

Please feel free to add more analytic to the motivation behind the question.

Thanks
Ankush

int mul(int x, int y)
{
if(y == 0)
return 0;
else
return x+mul(x,y-1)
}

def mul1(a, b, c):
	if c > b:
		return (0, b)
	else:
		p, b = mul1(a + a, b, c + c)
		return (p + a, b - c) if b >= c else (p, b)

def mul(a, b):
    return mul1(a, b, 1)[0]

can use recursive addition here. can get the result in log(n) steps of the multiplier

int mul(int m,int n)
{
	int v=0;
	if(n==1) return m;
	v = mul(m,n/2);
	v = v+v;
	if(n%2!=0) v+= m;
	return v;
}

Ok it seems there exists a solution which performs in O(log(min(m,n)). To the guy who raised the question, are you sure bitwise is also restricted.

a more tedious/clumsy answer:

int mult(int x, int y)
{
if (0 == x) return 0;
if (0 == y) return 0;

if ((x < 0) && (0 < y))
{
x= 0-x;
return 0 - (x+ mult(x, y-1));
}

if ((y < 0) && (0 < x))
{
y= 0-y;
return 0 - (x+ mult(x, y-1));
}

if ((y < 0) && (x < 0)) // both are negative
{
x= 0-x;
y= 0-y;
return (x+ mult(x, y-1));
}

// if we get here, both are positive
return (x+ mult(x, y-1));

}

from all above+ -ve check

int mul2(int m, int n)
{
if(n==1)return m;
int v=0;
v=mul2(m,n/2);
v=v+v;
(n%2==1)?v=v+m:0;
return v;
}

int mul(int m, int n)
{

int flag=0;
if(m==0||n==0) return 0;
if(n>m) swap(m,n);
if(m<0){m=0-m;flag++;}
if(n<0){n=0-n;flag++;}
return (flag%2==0)?mul2(m,n):(0-mul2(m,n));
}

int multiply(int a,int b)
{
   if(a==0 || b==0) return 0;

   if(b>0)
   {
      return a+multiply(a,b--);
   }
   else
   {
      a=-a;
      b=-b;
      return multiply(a,b);
   }
}

takes care of negative numbers as well

I came up with this version, take care of -ve as well

int main()
{
        int a = -4, b = 3;
        int result = a;
        mul(&result, a, b);
        cout << result << endl;
}

void mul (int *result, int num, int times){
        if( times == 1)
                return;
        *result += num;
        mul(result,num, times-1);
}

How about this?

int* mult(a, b)  //a times b 
         {
               int s;
               if ( b == 1) return a;
               mult(s+a , --b); 
              
         }

This worked for me.

int g_temp = 0;   //global

int mul(int a, int b)
{
        g_temp+=a; //increment a by a
        b--;      //b times

        if(b==0) return g_temp;
        else
        mul(a, b);      //recursively
}

Hi,

Just thought to summarize the possible motivation behind this question.
- Check to handle negative number.
- Check for minimum iteration
- Check for recursion concepts.
- Check for bitwise operators
- Check for O(Log N) solution by n/2 recursive solution
- Check for basic ideology of multiply, which is addition.
- Check for overflow condition handling. ( For C#, One can also read about checked keyword)

There are multiple variants of this question depending on the exact problem statement from interviewer. One can easily fit subset of above check's into the problem and come up with a robust source code.

Please feel free to add more analytic to the motivation behind the question.

Thanks
Ankush

int Mult(int a, int b)
{

}

int Mult(int a, int b)
{

}

int Mult(int a, int b)
{
if (b == 0) return 0;

int sub = Multi(a+a, b/2);
if (b % 2 == 1)
{
return sub + a;
}
else if (b % 2 == -1)
{
return sub - a;
}
return sub;
}

# include<iostream.h>
# include<math.h>
# include<conio.h>
int main()
{
int i,j;
double temp1,temp2,k;
cout<<"enter the first no"<<"\n";
cin>>i;
cout<<"enter next number"<<"\n";
cin>>j;
temp1=log10(i);
temp2=log10(j);
k=pow(10,temp1+temp2);
cout<<k;
getch();
return 0;

}

public static int multiplicationByAddition(int a, int b)
{
return (b < 0) ? -multiplycationRecursion(0, a, -b) : multiplycationRecursion(0, a, b);
}

private static int multiplycationRecursion(int sum, int a, int b)
{
if(b <= 0)
{
return sum;
}
else
{
return multiplycationRecursion(sum+=a, a, --b);
}

}

int mul(int a,int b)
{
int c=0;
if(abs(b)>abs(a))
{swap(a,b,c);}
printf("a=%d b=%d\n ",a,b);
if(b==1)
return a;
if(b==0 || a==0)
return 0;
if(b<0)
{
b=-b;
return -(a + mul(a,b-1));
}

return (a + mul(a,b-1));
}

int add(int a,int b)
{ return (a==0)?0:add(a>>1,b<<1)+(a&1)?b:0;
}