problem calculating the Maximum Pairwise Product C++

Question

This is my code for the maximum pairwise product. It takes an array of numbers, sorts them to find the first and second maximum numbers, then return the product of them. The code works for small arrays and small values. But it fails with some numbers, and also it epically fails with large numbers such as 10000 and so.

i thought it was a problem with the data type i used, so i defined the data type to be int_64t so it can handle large numbers, but still i get the same wrong results! Can anyone help me with that?

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

int64_t MaxPairwiseProduct(const std::vector<int64_t>& numbers) {

    int n = numbers.size();
    if(n<2)
        return;
int maxind1=-1;
for (int i=0; i<=n; i++)
{
    if(maxind1==-1 || numbers[i]>numbers[maxind1])
        maxind1=i;

int maxind2=-1;
for (int j=0; j<=n; j++)
   {

    if(maxind1!=j && maxind2==-1 || numbers[j]>numbers[maxind2])
    maxind2=j;}
int64_t restult=numbers[maxind1]*numbers[maxind2];
    return restult;
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int64_t> numbers(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> numbers[i];
    }

   cout << MaxPairwiseProduct(numbers) << "\n";
    return 0;
}

For example when i give it an array of 5 numbers consisting of 10000, 10,1,2,3..it's supposed to return 100000, instead it gives me some random large number, something like 17346274 or something. — Fezofchekov, Jun 23 '19 at 23:20
The error is here: `for (int j=0; j<=n; j++)`. Should be `j < n`. Same for another loop. — , Jun 23 '19 at 23:22
UPDATE: Now the code works fine with large numbers like 10000 and so, but it fails with small numbers! I tried a set of 3 numbers consisting of 1 2 3, it gave me a result of 9! while it was supposed to give 2*3=6, any ideas? — Fezofchekov, Jun 23 '19 at 23:55
What is the meaning of this line: `if(maxind1!=j && maxind2==-1 || numbers[j]>numbers[maxind2])`? It could be a precedence problem. You may want to add parenthesis. — , Jun 24 '19 at 00:14
Your curly braces don't match, I suppose there should be one at the end of the first loop. Please [edit] your question and fix that. And by the way, indentation is also broken. To avoid mistakes, copy the code from your editor, paste it here, select it, and press Ctrl-K. Thanks! — Fabio says Reinstate Monica, Jun 24 '19 at 00:15

v01d · Accepted Answer · 2019-06-24T07:49:28.753

3

(EDITED as per comments from others)

Besides what @dyukha noted - for (int j=0; j<=n; j++) - also: maxind2 could be negative in the code below, which is used to subscript the vector.

int maxind1=-1;
for (int i=0; i<=n; i++)
{
    if(maxind1==-1 || numbers[i]>numbers[maxind1])
        maxind1=i;

int maxind2=-1;
for (int j=0; j<=n; j++)
   {

    if(maxind1!=j && maxind2==-1 || numbers[j]>numbers[maxind2])

Solution is to change the precedence in logical expression inside if to:

if(maxind1!=j && (maxind2==-1 || numbers[j]>numbers[maxind2]))

edited Jun 24 '19 at 07:49

answered Jun 24 '19 at 00:03

v01d

189
1
12

Actually the first `if` is fine, because C++ uses [Short-circuit evaluation](https://en.wikipedia.org/wiki/Short-circuit_evaluation), which means that if `maxind1==-1` is true, the part after `||` is not even evaluated. But it's true that the second `if` has a problem: if `maxind1!=j` is false, it will evaluate `numbers[-1]`. Solution: use parentheses to change the precedence, that is, `if(maxind1!=j && (maxind2==-1 || numbers[j]>numbers[maxind2]))`. Which is, by the way, what Chipster said in the comments. – Fabio says Reinstate Monica Jun 24 '19 at 00:38
@FabioTurati yes I didn't pay attention on the first. Also, didn't know the (what i see as standard logical ops) are called short-circuit. – v01d Jun 24 '19 at 00:45
In a logical OR, if the first is true, then you are sure the whole OR expression will be true, and this is due to the very nature of OR. It is like this in every language. What short-circuiting adds is that, in such cases, the second part is not even evaluated, as it would be a waste of time. This prevents some problems, as in this case. A typical example, when you have a pointer `p`, is: `if (p && p->do_something())`. If `p` is null, evaluating the second part would lead to Undefined Behaviour (probably a segmentation fault), but short circuiting prevents it and makes this code safe to run. – Fabio says Reinstate Monica Jun 24 '19 at 00:54
@FabioTurati understand that, but I never heard term "short-circuit" is what's this called, or that that's a feature. I thought that's standard logic – v01d Jun 24 '19 at 00:55
Well, most languages support short-circuiting, but not all: https://stackoverflow.com/questions/1232603/do-all-programming-languages-have-boolean-short-circuit-evaluation. So I wouldn't call it "standard logic". In any case, back to your answer: I'd suggest you to [edit] it and remove the part about `maxind1`. You could also add how to solve the problem about `maxind2`. Feel free to take it from my comment, if you want! – Fabio says Reinstate Monica Jun 24 '19 at 01:06
The problem was indeed with the parenthesis in the if conditions. It works perfectly now. Thank you. – Fezofchekov Jun 24 '19 at 03:11
@FabioTurati Thank you , I will do so – v01d Jun 24 '19 at 07:37
1

@Rania Please remember that if an answer solves your problem you should mark it as accepted, by clicking on the tick on its left. Thank you! – Fabio says Reinstate Monica Jun 24 '19 at 08:59

score 1 · Answer 2 · answered Jun 24 '19 at 03:20

SOLVED Thank you all for helping me out, it finally worked properly. The source of the problem was that i didn't use parenthesis in the second if conditions, and the condition of the for loop (use < instead of <=) Code after solving the errors:

#include <cstdlib>
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

int64_t MaxPairwiseProduct(const std::vector<int64_t>& numbers) {

    int n = numbers.size();


int maxind1=-1;
for (int i=0; i<n; i++)
{
    if(maxind1==-1 || numbers[i]>numbers[maxind1])
        maxind1=i;
}
int maxind2=-1;
for (int j=0; j<n; j++)
   {

    if(j!=maxind1 && (maxind2==-1 || numbers[j]>numbers[maxind2]))
    maxind2=j;}
int64_t restult=numbers[maxind1]*numbers[maxind2];
    return restult;
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int64_t> numbers(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> numbers[i];
    }

   cout << MaxPairwiseProduct(numbers) << "\n";
return 0;}

problem calculating the Maximum Pairwise Product C++

2 Answers2