Multiplying two large vector variables

Question

The following code is to find the Maximum Pairwise Product (MPP) which is:

You're given an array of N integers and a number K. The maximum K-product of the array is the maximum product of any K length subsequence of the array. For example, the maximum 2-product of the array [-5, 3, 4, -6] is 30 because the product of the subsequence [-5, -6] is 30 and it is impossible to achieve a larger subsequence products.

The code below calculates the MPP for every input except for "90000 and 100000" which must give an output 9,000,000,000, but I got 410065408:

int MaxPairwiseProduct(const vector<int>& numbers) {
    int result = 0;
    int n = numbers.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (numbers[i] * numbers[j] > result && numbers[i] * numbers[j] % 2 == 0) {
                result = numbers[i] * numbers[j];
            }
        }
    }
    return result;
}

Sadly, these pages (1 and 2) did not help me with my request.

I am suggesting that an `int` on your system may not be able to store the value 9,000,000,000. — JFMR, Dec 19 '17 at 20:01
BTW, You can have better algorithm. result is the maximum between the product of the 2 biggest numbers or the 2 lowest. — Jarod42, Dec 19 '17 at 20:09
Can you show your new resulting code ? (better in a new question as not really related to this question). — Jarod42, Dec 19 '17 at 20:34
Please in code questions give a [mre]--cut & paste & runnable code; example input (as initialization code) with desired & actual output (including verbatim error messages); tags & versions; clear specification & explanation. That includes the least code you can give that is code that you show is OK extended by code that you show is not OK. (Debugging fundamental.) — philipxy, Sep 22 '19 at 07:28

score 2 · Accepted Answer · edited Sep 24 '19 at 00:19

2

Because when you multiply your integer, it is outgoing of the int type boundaries. In this case, use the long long type:

long long MaxPairwiseProduct(const vector< long long >& numbers) {
long long result = 0;
int n = numbers.size();
for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
        if (numbers[i] * numbers[j] > result && numbers[i] * numbers[j] % 2 == 0) {
            result = numbers[i] * numbers[j];
        }
    }
}
return result;

Please note that if your numbers are too big (bigger than 2^63-1) you can not use standard C++ types. There is all type boundaries C++ data types.

edited Sep 24 '19 at 00:19

Peter Mortensen

30,738
21
105
131

answered Dec 19 '17 at 20:00

Bakhrom Rakhmonov

692
6
15

4

Those "C++ data types" are what Microsoft's 2015 compiler does. That does not mean that every compiler will do that. C++ allows a much larger set of possible ranges. – Pete Becker Dec 19 '17 at 21:13
**long long** does not help! I used **long long int** and worked well for me – Sep 02 '19 at 11:37
1

[`long long` and `long long int` are identical](https://stackoverflow.com/a/18971763) (potentially with the exception if you use a non-standard compiler, or a compiler with really weird behavior that treats the two as different types. It's not supposed to) – Zoe Sep 21 '19 at 12:20

Multiplying two large vector variables

1 Answers1