3
\$\begingroup\$

I saw this interview question and decided to solve using recursion in Java.

Write a multiply function that multiples 2 integers without using *

public class Main {

  public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    System.out.println("Enter first num: ");
    double num = in.nextDouble();
    System.out.println("Enter second num: ");
    double numTwo = in.nextDouble();

    System.out.println(multiply(num, numTwo));
  }

  private static double multiply(double x, double y) {

    if (x == 0 || y == 0) {
      return 0;
    } else if (y > 0) {
      return x + multiply(x, y - 1);
    } else if (y < 0) {
      return -multiply(x, -y);
    } else {
      return -1;
    }
  }
}

What should I return instead of -1 to make this clear?

\$\endgroup\$
4
\$\begingroup\$

What should I return instead of -1 to make this clear?

Don't return -1, but recognise that you have exhausted the possible states of y, so simply do a return for the last possibility.

private static double multiply(double x, double y) {
    if (x == 0 || y == 0) {
        return 0;
    } else if (y > 0) {
        return x + multiply(x, y - 1);
    }
    return -multiply(x, -y);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Since y is a double, testing y == 0, y > 0, and y < 0 doesn't exhaust the possible states. There's also Double.isNaN(y). \$\endgroup\$ – Peter Taylor Apr 26 '17 at 15:14
4
\$\begingroup\$

The challenge only requires you to work with integers. This technique would not actually be able to multiply two floating-point numbers, so don't use double. A proper solution for integers would not have a failure node that requires you to return -1.

A better algorithm to use would be the Russian peasant method which can be done by bitwise operations and addition.

\$\endgroup\$
  • \$\begingroup\$ What should I use to not to get "stackoverflow error" with huge numbers? \$\endgroup\$ – Egek92 Mar 9 '17 at 15:57
  • \$\begingroup\$ The Russian peasant method is much more efficient, and would not cause stack overflow. \$\endgroup\$ – 200_success Mar 9 '17 at 16:01
0
\$\begingroup\$

I fully agree with @200_success' answer. But I wouldn't remember the russian peasant method when asked this interview question. And I doubt they would give me enough time to look it up on the internet.

So let's look at your algorithm to solve it but try to reduce the recursion to a minimum.

The usual way to write a method like this is to first handle the special cases and quickly return, then handle the normal calculations.

I would write the method like this:

private static int multiply (int x, int y) {
    if(x == 0 || y == 0){
        return 0;
    }
    if(x < 0) {
        return -multiply(-x, y);
    }
    int result = 0;
    for(int i = x; i > 0; i--){
        result += y;
    }
    return result;
}

Here I first handled the trival cases of multiply-by-zero. Then the special case where x is negative. I did use recursion here, because it makes handling the case really easy and only goes exactly 1 step deeper.

Then the actual algorithm literaly says: for x times, add y to the result. I swapped the logic around compared to your solution because it's the actual meaning of x * y.

\$\endgroup\$
-1
\$\begingroup\$

As these are integers, a naive solution to add one input over and over again in a for loop indexed from 0 to the other input - 1. You have to handle negatives as well.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.