Multiply two numbers

Question

I am trying to implement multiplication of two numbers without using the * operator, as a practice for programming interviews. I have written two functions.

1) Using Long Multiplication

    static int MultiplyTwoNumbers(int num1,int num2)
    {
        List<int> leftnumber = new List<int>();
        do
        {
            leftnumber.Add(num1% 10);
            num1/= 10;
        } while (num1!=0);

        List<int> rightnumber = new List<int>();

        do
        {
            rightnumber.Add(num2% 10);
            num2/= 10;
        } while (num2!= 0);


        int result = 0;
        int counter = 1;
        for (int i = 0; i <leftnumber.Count; i++)
        {
            int tempresult = 0;
            int carry = 0;
            int innercounter = counter;
            for (int j = 0; j<rightnumber.Count; j++)
            {
                int tempVal = leftnumber[i] * rightnumber[j];
                tempVal += carry;
                if (tempVal / 10 != 0)
                {
                    carry = tempVal / 10;
                    tempVal = tempVal % 10;
                }
                tempresult = tempresult + (innercounter * tempVal);
                innercounter = innercounter * 10;
            }

            result +=tempresult;
            counter = counter * 10;
        }

        return result;



    }

2) using Addition

  static int multiplicationUsingAdd(int num1,int num2)
    {
        int result = 0;
        for (int i = 0; i < num2; i++)
        {
            int temp=result+ num1;
            result = temp;
        }
        return result;
    }

Which one is better and how can I improve it ?

Answer 1

You seem to be very much over-complicating this. Here is an efficient solution:

Assuming a and b are positive numbers and the result is a valid 32-bit integer value

public int Multiply(int a, int b)
{
    if (a < 0 || b < 0)
        throw new ArgumentException("Numbers must be positive");

    var min = Math.Min(a, b);
    var max = Math.Max(a, b);

    if (min == 0 || max == 0)
        return 0;
    else if (min == 1)
        return max;

    int s = min >> 1;
    int halfProduct = Multiply(s, max);

    if (min % 2 == 0)
        return halfProduct + halfProduct;
    return halfProduct + halfProduct + max;
}

So what is happening here? First we need to sort these by the smaller and larger numbers, this reduces the number of iterations required. If either of the numbers is zero, then we return zero (since x*0 == 0). If the minimum number is 1, then we return max (since x*1 == x).

Now we can apply the shift operator since shifting one to the right divides the number by 2. By recursion we keep doing this until Multiply returns 0 or max. We can then determine the value if min is even by adding the two half-products or if min is odd by adding the two half products and max.

Again, even in your original solution this will break for negative numbers. You can code around that by switching the sign (Math.Abs) and swapping the sign at the end (0 - return value, unless both are negative then you leave it positive). I'll leave that as an exercise for you.

Answer 2

It breaks if num2 is negative

static int Multiply(int num1, int num2)
{
    var result = 0;

    for (int i = 0; i < Math.Abs(num2); i++)
    {
        result += num1;
    }

    if (num2 < 0)
    {
        return -result;
    }
    else
    {
        return result;
    }
}

Answer 3

I am trying to implement multiplication of two numbers. And I am looking to improve its time and space efficiency

There really isn't a better time and space efficiency than this.

static int MultiplyTwoNumbers(int num1, int num2)
{
    return num1 * num2;
}

However, I assume that you've got some other motives behind the question.

Which one is better and how can I improve it?

Of the two methods you've posted, multiplicationUsingAdd is clearly the better option for a few reasons:

1. It's simpler and easier to understand.
2. There's no memory allocation on the heap (like the new List<int>()) in the other one.
3. I haven't profiled it, but it's extremely likely to be the faster of the two.

However, it could be improved quite a bit.

1. Standard C# naming conventions always use PascalCase for method names. It should be called MultiplicationUsingAdd
2. The name MultiplicationUsingAdd is a form of leaky abstraction because the method name exposes the details of the implementation.
3. A better name would simply be Multiply. The parameters indicate how many numbers are involved and the implementation details are irrelevant.
4. The code itself can be make a little easier to read by removing some irrelevant bits (e.g. the temp variable).

Here's how I would have written it.

static int Multiply(int num1, int num2)
{
    var result = 0;

    for (int i = 0; i < num2; i++)
        result += num1;

    return result;
}