Summing the Product of Array-member combinations

Question

Find the sum of product of all numbers in first array with all the numbers in second array.

Input Format

• 1st line contains 2 space separated integers N and M.
• 2nd line contains N space separated integers Ai.
• 3rd line contains M space separated integers Bi.

Output Format

• 1 single line containing only the required answer.

#include<iostream>
using namespace std;

int sum(int product)
{
    static int temp = 0;
    temp = temp + product;
    return temp;
}

int main()
{
    int N, M, result, i, j;
    cin>>N>>M;
    int *a1, *a2;
    a1 = new int[N];
    a2 = new int[M];
    for(i = 0; i < N; i++)
        cin>>a1[i];
    for(i = 0; i < M; i++)
        cin>>a2[i];

    for(i = 0; i < N; i++)
    {
        for(j = 0; j < M; j++)
            result = sum(a1[i]*a2[j]);
    }
    cout<<result;
    return 0;
}

Answer 1

Your performance problem here is related to a number of things, but the most significant is the algorithm you use.

Consider the following math:

ax + bx + cx + dx ... == x(a + b + c + d + ...)

Using that logic, the basic math for one array can be simplified.... for example, you can take the second array, sum up the values, and call that sum x.

Now you just need to take all the values in the first array, and multiply them by the sum of the second array, instead of summing the individual products.

As it happens, you can take the same logic, and apply it the other way as well. Bottom line, is that the solution is simply the product of the sums of the arrays:

#include <iostream>

int sum(int count) {
    int tmp, sum = 0;
    for (int i = 0; i < count; i++) {
        std::cin >> tmp;
        sum += tmp;
    }
    return sum;
}

int main() {
    int N, M;
    std::cin >> N >> M;
    int suma = sum(N);
    int sumb = sum(M);
    int result = suma * sumb;
    std::cout << result << "\n";
    return 0;
}

Note, that:

1. the above code no longer uses "using namespace std;"
2. The sum method no loger uses static variables. Those are a bad idea especially when it comes to re-entrant code.
3. Output a newline after the last line.