Multiplying 2 numbers without using * operator in Java

Question

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?

Answer 1

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);
}

• Peter Taylor: 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).

Answer 2

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.

• user127004: What should I use to not to get "stackoverflow error" with huge numbers?
• 200_success: The Russian peasant method is much more efficient, and would not cause stack overflow.

Answer 3

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.

Answer 4

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.