Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
I am not sure whether it works for negative numbers..I.e. try Mul(-11, -11), expected result is 121...
The question said no multiplication operation, so doing
return sign?-ans:ans;
is using the -1 * ans isn't it?
Shouldn't it be
sign ? ~ans + 1 : ans
Is negating something considered multiplying by the compiler?
And yes,
~ans +1
should correctly flip the sign as well.
A good optimization here is to use the smaller of a and b as the loop index (i.e. swap a and b if b < a). For large values of a/b, you can optimize this even further by doing it in log(N) time if the interview allows you bit shifts. Something like this:
if a == 0: return 0
if a == 1: return b
half_a = a >> 2
rem_a = a % 2
sum_half_a = sum(half_a, b)
if rem_a == 1:
return b + sum_half_a + sum_half_a
else:
return sum_half_a + sum_half_a
Michael's being a little bit snarky, but if we're gonna assume our computer's too crippled to do multiplication, why wouldn't we break out the slide rule? ;)
To convert from positive number to negative number, the following should work, correct?
number = 0 - number;
int multiply( int a, int b) {
if (a==0 || b==0)
return 0;
int sign = 0, result;
if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
sign = 1;
}
int a1 = abs(a);
int b1 = abs(b);
while (b1--) {
result + = a1;
}
if (sign) {
return result/(-1);
} else {
return result;
}
}
You are not allowed to multiply or even divide. If you could use divide you could simply use res = a/(1/b);
:)
Following does it with no multiply or divide and with least possible iterations.
private static int multiply(int a, int b) {
if(a == 0 || b == 0)
return 0;
int res = 0;
int absA = Math.abs(a);
int absB = Math.abs(b);
if ((a > 0 && b > 0) || (a < 0 && b < 0)) {
a = absA;
b = absB;
}
if( absA > absB) {
while(absB > 0) {
res+=a;
absB--;
}
} else {
while(absA > 0) {
res+=b;
absA--;
}
}
return res;
}
The question does not say that you can't use divide. So I guess 1/a/b solution might be OK.
@ Simpleone: Your code has a bug, try passing in (-1, 1) or (-1,2) and it will return a +ve integer. Just tweaked your code and verified that it works, changed return type to double to avoid overflow on int.maxvalue. Updated code is in c#. Edited - just for the heck of it added a way to do the same for an array of values.
protected internal static double Multiply(int a, int b)
{
if (a == 0 || b == 0) return 0;
double res = 0;
int absA = Math.Abs(a);
int absB = Math.Abs(b);
if (absA > absB)
{
while (absB > 0)
{
res += absA;
absB--;
}
}
else
{
while (absA > 0)
{
res += absB;
absA--;
}
}
if ((a > 0 && b < 0) || (a < 0 && b > 0))
{
res = -res;
}
return res;
}
/// <summary>
/// Method that receives an integer array and returns the product without using mutliply or divide operators.
/// </summary>
protected internal static double MultiplyArray(int[] a)
{
if (a.Length == 0 || a.Contains(0)) return 0;
int iNeg = 0;
int iPos = 0;
int iL = a.Length;
for (int i = 0; i < iL; i++)
{
if (a[i] < 0) iNeg++;
else iPos++;
a[i] = Math.Abs(a[i]);
}
Array.Sort<int>(a);
double res = a[0];
for (int i = 1; i < iL; i++)
{
res = Multiply((int)res, a[i]);
}
if (iNeg!=iPos)
{
res = -res;
}
return res;
}
public class Solution {
public static int multiply(int a, int b) {
if (a == 0 || b == 0) {
return 0;
}
if (b == 1) {
return a;
}
boolean positiveFlag = true;
if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
positiveFlag = false;
}
a = Math.abs(a);
b = Math.abs(b);
if (a < b) {
a ^= b;
b ^= a;
a ^= b;
}
int ret1 = multiply(a, b/2);
int ret2 = multiply(a, b%2);
if (positiveFlag == false) {
return -(ret1+ret1+ret2)
}
else {
return ret1+ret1+ret2;
}
}
}
Well you are getting the right result but what was the reason for doing all these computations? Can you please explain.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Multiply
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(Multiply(11,11));
}
private static int Multiply(int a, int b)
{
int result = 0;
while (true)
{
if (b == 1)
{
result = result + a;
break;
}
else if((b % 2) != 0)
{
result = result + a;
}
a = a + a;
b = b / 2;
}
return result;
}
}
}
int multiply(int a, int b)
{
if(b == 0)
return 0;
if(b > 0)
return a + multiply(a, b-1);
if(b < 0)
return (-a) + multiply(a, b+1);
}
public static int multiply(int a, int b){
if(a==0||b==0) return 0;
int sign = 0;
if(((a>>31) &0x1) == 1){
sign = 1;
a = ~a + 1;
}if(((b>>31) & 0x1) == 1){
if (sign == 0)sign = 1;
else sign = 0;
b = ~b + 1;
}
int mul = 0;
//System.out.println(b + " "+ a);
while(b>0){
if((b & 0x1) > 0){
mul +=a;
}
b = b>>1;
a = a<<1;
}
if (sign ==1)
return ~mul + 1 ;
return mul;
}
Lucky Fellow to get this question
int Multiply(int number, int multiple)
{
int num=number;
while(multiple--)
number=number+num;
retrun number;
}
/**
*
* PropertiesFor the natural numbers, integers, fractions, and real and complex numbers, multiplication has certain properties:
Commutative property : x*y=y*x;
The order in which two numbers are multiplied does not matter;
Associative property : (x*y)*z=x*(y*z);
Expressions solely involving multiplication are invariant with respect to order of operations;
Distributive property : x*(y+z) = x*y+x*z;
Holds with respect to multiplication over addition. This identity is of prime importance in simplifying algebraic expressions:
Identity element : x*1=x;
The multiplicative identity is 1; anything multiplied by one is itself. This is known as the identity property:
Zero element : x*0=0;
Any number multiplied by zero is zero. This is known as the zero property of multiplication:
Zero is sometimes not included amongst the natural numbers.
There are a number of further properties of multiplication not satisfied by all types of numbers.
Negation : x*-1 = -x;
Negative one times any number is equal to the opposite of that number.
-1*-1=1;
Negative one times negative one is positive one.
The natural numbers do not include negative numbers.
Inverse element
Every number x, except zero, has a multiplicative inverse, , such that .
The natural numbers and integers do not have inverses.
Exculding folating and complex numbers mulitple
*/
public static long mulitple (int a, int b){
long mulitplicationResult = 0;
boolean isPositiveResult = false;
// Retrun zero if any one input has zero
if (a == 0 || b==0){
return mulitplicationResult;
}
//Sign calculation of result
if( (a<0 && b<0) || (a>0 && b>0) ){
isPositiveResult = true;
}else{
isPositiveResult = false;
}
//Converting -ve values of the input into +ve
if(a<0) a=(~a+1);
if(b<0) b=(~b+1);
//For example: 3 multiplied by 4 can also be calculated by adding 3 copies of 4 together.
while( b>0 ){
mulitplicationResult += a;
b--;
}
return isPositiveResult?mulitplicationResult:(~mulitplicationResult+1);
}
suppose we have a , b
1) First produce arr[9] where arr[i]=i*a , (1<=i<=9). we can do it with 9 addition.
2) For each digit in b[i]=k add i zero on right-side of the arr[k] and add them to each other.
The result is a*b.
It is the obvious way that we calculate multiply on paper!
This solution is useful for bignumber multiplication too.
this is a solution in java and it doesn't involve a loop, the answer is pretty simple:
public class Multiply{
public static void main (String[] args){
System.out.println("The result is:" + multiply(5,-13));
}
private static int multiply(int i, int j) {
double k = i;
double l = j;
return (int)(k/(1/l));
}
}
This solution works if multiplication is among either positive or negative numbers. The ~ operator is used just to make positive number to negative and negative number to positive
// multiply 2 no without using mul operat.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<stdio.h>
using namespace std;
void main()
{
int a, b;
int flag1=0,mul=0;
int flag2=0;
printf("enter the two numbers\n");
scanf_s("%d%d",&a,&b);
if(a<0)
{
flag1=1;
a=~(a)+1;
}
if(b<0)
{
flag2=1;
b=~(b)+1;
}
for(int i=0;i<b;i++)
{
mul=mul+a;
printf("the mul inside for loop %d\n",mul);
}
if(flag1==1 || flag2==1)
{
if(flag1==1 && flag2==1)
{
printf("both numbers are negative\n");
}
else
{
mul=~(mul)+1;
}
}
printf("%d",mul);
}
Can any one help me to find the multiplication of two floating point numbers without using * operator or any library fn that uses * internally....
I think we can take the integral & fractional part separately and multiply like above mentioned code for integral part. But m having difficulty with fractional part ...But if any one can help me to identify the bit position of fractional part in float, then it can be done easily....
Thanks in advance...
public int sum(int a, int b) {
int result = a ^ b;
int carry = a & b;
while (carry != 0) {
carry <<= 1;
int x = result;
result ^= carry;
carry &= x;
}
return result;
}
public int multiply(int a, int b) {
int result = 0;
if (a == 0 || b == 0) {
return result;
}
boolean negative = a > 0 && b > 0 || a < 0 && b < 0 ? false : true;
a = a > 0 ? a : -a;
b = b > 0 ? b : -b;
int k = 0;
while (b != 0) {
if ((b & 1) > 0) {
result = sum(result, a << k);
}
k++;
b = b >>> 1;
}
if (negative)
result = sum(~result, 1);
return result;
}
method with a helper function
def multiply(a,b):
sign = (a<0 and b < 0) or (a>0 and b> 0)
def multiplyHelper(a,b):
if b == 0 or a == 0:
return 0
if b%2 == 0:
return multiplyHelper(a, b/2) + multiplyHelper(a, b/2)
else:
return a + multiplyHelper(a, b-1)
ans = multiplyHelper(abs(a), abs(b))
return ans if sign else ~ans+1
assert 35 == multiply(-7,-5)
assert -35 == multiply(-7, 5)
private static int multiply(int a, int b) {
if(a == 0 || b == 0)
return 0;
int res = 0;
int absA = Math.abs(a);
int absB = Math.abs(b);
if ((a > 0 && b > 0) || (a < 0 && b < 0)) {
a = absA;
b = absB;
}
if( absA > absB) {
while(absB > 0) {
res+=a;
absB--;
}
} else {
while(absA > 0) {
res+=b;
absA--;
}
}
return res;
}
@ Simpleone: Your code has a bug, try passing in (-1, 1) or (-1,2) and it will return a +ve integer. Just tweaked your code and verified that it works, changed return type to double to avoid overflow on int.maxvalue. Updated code is in c#. Edited - just for the heck of it added a way to do the same for an array of values.
protected internal static double Multiply(int a, int b)
{
if (a == 0 || b == 0) return 0;
double res = 0;
int absA = Math.Abs(a);
int absB = Math.Abs(b);
if (absA > absB)
{
while (absB > 0)
{
res += absA;
absB--;
}
}
else
{
while (absA > 0)
{
res += absB;
absA--;
}
}
if ((a > 0 && b < 0) || (a < 0 && b > 0))
{
res = -res;
}
return res;
}
/// <summary>
/// Method that receives an integer array and returns the product without using mutliply or divide operators.
/// </summary>
protected internal static double MultiplyArray(int[] a)
{
if (a.Length == 0 || a.Contains(0)) return 0;
int iNeg = 0;
int iPos = 0;
int iL = a.Length;
for (int i = 0; i < iL; i++)
{
if (a[i] < 0) iNeg++;
else iPos++;
a[i] = Math.Abs(a[i]);
}
Array.Sort<int>(a);
double res = a[0];
for (int i = 1; i < iL; i++)
{
res = Multiply((int)res, a[i]);
}
if (iNeg!=iPos)
{
res = -res;
}
return res;
}
Try something like this:
public int myMethod(int i, int j) {
int x = 0;
if (j >= 0) {
for (int k = 1; k <= j; k++) {
x = x + i;
}
return x;
} else if ((i < 0) && (j < 0)) {
for (int k = 1; k <= -i; k++) {
x = x + j;
}
return (-x);
} else {
for (int k = 1; k <= i; k++) {
x = x + j;
}
return x;
}
}
The function should return long for two int.
long mulwithoutmul(int a, int b)
{
long res=0;
long la;
int i;
char neg = ((a^b)>>31);
a = abs(a);
b = abs(b);
if(a == 0 || b == 0)
return 0;
la = a;
for(i = 0 ; i < 31 ; i++)
{
if((b>>i)&0x00000001)
res+=la<<i;
}
if(neg)
{
res = 0-res;
}
return res;
}
!python
def multiply(x, y):
if x == 0 or y == 0: return 0
negative = False
if x < 0 and y < 0: x = -x; y = -y;
elif x < 0: x = -x; negative = True
elif y < 0: y = -y; negative = True
# Small optimization
add_value = x
counter_range = y
if y > x: add_value = y; counter_range = x
value = 0
for i in range(counter_range):
value = value + add_value
return -value if negative else value
why not a recursive algo like this?
public static int simpleMultiply(int one, int two)
{
if(two==0 || one ==0)
return 0;
if(one>0 && two>0)
{
return one+simpleMultiply(one,two-1);
}
else
if(one<0 && two <0)
{
return simpleMultiply(0-one,0-two);
}
else
if(one<0 && two >0)
{
return simpleMultiply(0-one,0-two);
}
else
if(one>0&&two<0)
{
return (0-one)+simpleMultiply(one,two+1);
}
return 0;
}
public class convert {
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(multiply(10,300));
}
private static int multiply(int a, int b) {
int result=0;
if(a>b)
{
for(int i=1;i<=b;i++)
{
result= add(result,a);
}
}
else
{
for(int i=1;i<=a;i++)
{
result= add(result,b);
}
}
return result;
}
private static int add(int a, int b) {
int carry=0;
while(b!=0)
{
carry=a&b;
a=a^b;
b=carry<<1;
}
return a;
}
}
- duckling February 25, 2013