Integers multiplication

Write a function that multiply two integers without using multiplication or division, you can assume that both integers are even.

What’s the best runtime that you can come up with?

Approach

Given input integers S and B, where S being the smaller integer and B being the bigger: The brute force approach would be to iterate S times and add B to the result in every iteration. The runtime for this is O(S).

We can improve the runtime to O(LogS) by following this process:

• Divide the smaller number by 2. We can divide by 2 without using the division operator by moving the bits one step to the right (number >> 1).
• Calculate the results
• Multiply the result by two, by adding the result to itself (result + result)
• Repeat the process again and again.

Let’s evaluate the stack with a small example: given S=4 and B=5

We call multiplyRecursive with (4, 5)

• multiplyRecursive (depth 1) divide 4 by 2, and call itself with (2, 5)
• multiplyRecursive (depth 2) divide 2 by 2, and call itself with (1, 5)
• multiplyRecursive (depth 3) just hit its base case, it returns 5 (the bigger number)
• multiplyRecursive (depth 2) returns 5 + 5 = 10
• multiplyRecursive (depth 1) returns 10 +10

The result is 20.

What will happen if the smaller number is 10?

Tests

public class IntMultiplyTest {
    @Test
    public void multiply_even() throws Exception {
        final int n1 = 2;
        final int n2 = 4;
        final int result1 = IntMultiply.multiply(n1, n2);
        assertEquals(n1 * n2, result1);
    }

    @Test
    public void multiply_odd() throws Exception {
        final int n1 = 2;
        final int n2 = 3;
        final int result1 = IntMultiply.multiply(n1, n2);
        assertEquals(n1 * n2, result1);
    }

    @Test
    public void multiply_smallerAfterBigger() throws Exception {
        final int n1 = 6;
        final int n2 = 4;
        final int result1 = IntMultiply.multiply(n1, n2);
        assertEquals(n1 * n2, result1);
    }

    @Test
    public void multiply_evenBig() throws Exception {
        final int n1 = 12;
        final int n2 = 10;
        final int result1 = IntMultiply.multiply(n1, n2);
        assertEquals(n1 * n2, result1);
    }

    @Test
    public void multiply_oddBig() throws Exception {
        final int n1 = 30;
        final int n2 = 25;
        final int result1 = IntMultiply.multiply(n1, n2);
        assertEquals(n1 * n2, result1);
    }

    @Test
    public void multiply_rangeOfSmallers() throws Exception {
        int n1 = 0;
        final int n2 = 25;

        for (int i = 0; i < 100; i++) {
            final int result1 = IntMultiply.multiply(n1, n2);
            assertEquals(n1 * n2, result1);

            n1++;
        }
    }

    @Test
    public void multiply_zero() throws Exception {
        final int n1 = 0;
        final int n2 = 25;
        final int result1 = IntMultiply.multiply(n1, n2);
        assertEquals(n1 * n2, result1);
    }
}

Solution?

How about this solution.

public class IntMultiply {
    public static int multiply(int n1, int n2)
    {
        final boolean n1IsBigger = n1 > n2;
        int bigger = n1IsBigger ? n1 : n2;
        int smaller = n1IsBigger ? n2 : n1;

        int result = multiplyRecursive(smaller, bigger);

        return result;
    }

    public static int multiplyRecursive(int smaller, int bigger){
        // Base cases
        if (smaller == 0) {
            return 0;
        } else if (smaller == 1) {
            return bigger;
        }

        // divide by two
        final int smallerDividedByTwo = smaller >> 1;

        int halfResult = multiplyRecursive(smallerDividedByTwo, bigger);

        int result = halfResult + halfResult;
        return result;
    }
}

This solution will work, for numbers like 2, 8, 16,  but would it work for 10?

No, it wouldn't. After we divide 10 by 2 once, we get an odd number (5). Luckily we tested the code with variety of numbers...

Solution!

The fix is simple. Before calling the recursion, if the smaller number is odd, we decrease it by one to make it even. When the recursion is done, we fix the result by adding the bigger number.

public class IntMultiply {
    public static int multiply(int n1, int n2)
    {
        final boolean n1IsBigger = n1 > n2;
        int bigger = n1IsBigger ? n1 : n2;
        int smaller = n1IsBigger ? n2 : n1;

        int result = multiplyRecursive(smaller, bigger);

        return result;
    }

    public static int multiplyRecursive(int smaller, int bigger){
        // Base cases
        if (smaller == 0) {
            return 0;
        } else if (smaller == 1) {
            return bigger;
        }

        Boolean smallerIsOdd = smaller % 2 == 1;
        if (smallerIsOdd){
            // If smaller is odd, make it even
            smaller--;
        }

        // divide by two
        final int smallerDividedByTwo = smaller >> 1;

        int halfResult = multiplyRecursive(smallerDividedByTwo, bigger);

        int result = halfResult + halfResult;
        if (smallerIsOdd){

            // If smaller was odd, we need to fix the result
            result += bigger;
        }

        return result;
    }
}