[Moderate] interview questions #9

[rygh4775]

Operations: Write methods to implement the multiply, subtract, and divide operations for integers. The results of all of these are integers. Use only the add operator.

[rygh4775]

Multiplication

• Num1 * num2 -> Add num1 to itself num2 times

int abs(int num) {
    if(num < 0) {
    return negate(num);
  } else {
    return num;
  } 
}

int multiply(int num1, int num2) {
    if(abs(num1) < abs(num2)) {
    return multiply(num2, num1);
  }
  int sum = 0;
  for(int i = 0; i <= abs(num2); i++) {
    sum =+ num1;
  }
  if(num2 < 0) {
    sum = negate(sum);
  }
  return sum;
}

Subtraction

• num1 - num2 -> *num1 + (-1) num2**

int negate(int num) {
  int neg = 0;
  int newSign =  num < 0 ? 1 : -1;
  while( num != 0) {
    neg += newSign;
    num += newSign;
  }
  return neg;
}

int substract(int num1, int num2) {
  return num1 + negate(num2);
}

• Time complexity: O(N), N is the absolute numner of num2.

Division

• num1 / num2 = x - > num1 = num2 * x

int divide(int num1, int num2) {
  if(num2 == 0) {
    throw new java.lang.ArithmeticException("ERROR");
  }
  int absNum1 = abs(num1);
  int absNum2 = abs(num2);

  int times = 0;
  int sum = 0;
  while(sum + absNum2 < absNum1) {
    sum += absNum2;
    times++;
  }

  if((num1 < 0 && num2 < 0) || (num1 > 0 && num2 > 0)) {
    return times;
  } else {
    return negate(times); 
  }
}

Improvement

For example:

29 | 28 | 26 | 22 | 14 | 13 | 11 | 7 | 6 | 4 | 0 <- num

​ -1 | -2 | -4 | -8 | -1 | -2 | -4 | -1| -2 | -4 <- delta

The code below implements this algorithm.

int negate(int num) {
 int neg = 0;
 int newSign = num < 0 ? 1 -1;
 int delta = newSign;

 while (num != 0) {
  boolean differentSigns = (num + delta > 0) != (num > 0);
  if (num + delta != 0 && differentSigns) { // If delta is too big, reset it .
   delta = newSign;
  }
  neg += delta;
  a += delta;
  delta += delta; // Double the delta
 }
 return neg;
}