I have to find the maximum sum of 4 numbers from an array of 5. My code fails for bigger numbers

Question

I had to find the maximum sum of 4 numbers from an array of 5, and a minimum sum in the same way. My code fails for some of the bigger test cases as the maxsum for some reason goes to negative

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

int minimini(int list[]){
    int minisum=0;
    int taker;
    int a=max({list[0],list[1],list[2],list[3],list[4]});
    for (int i=0; i<5; i++){
        taker=list[i];
        if(taker!=a){
            minisum=minisum+taker;
        }
    }
return minisum;
}
int maxa(int list[]){
    int maxsum=0;
    int taker;
    int a=min({list[0],list[1],list[2],list[3],list[4]});
    for (int i=0; i<5; i++){
        taker=list[i];
        if(taker!=a){
            maxsum=maxsum+taker;
            cout<<"maxsum >>"<<maxsum;
            cout<<"a="<<a;
        }
    }
return maxsum;
}
int main(){
    int list[5];
    int minisum, maxsum;
    for (int i=0; i<5; i++){
        cin>>list[i];
    }

    minisum=minimini(list);
    maxsum=maxa(list);

    cout<<minisum<<" "<<maxsum;


    return 0;
}

Ever thought what happens when you have multiple copies of min/max element in the list? — ALX23z, Jan 08 '20 at 06:34
You could sort the array of 5 (e.g. with `std::sort`). Then the minimum sum is the sum of the first 4 elements and the maximum sum the sum of the last 4, isn't it? — Scheff's Cat, Jan 08 '20 at 06:41
_My code fails for some of the bigger test cases_: Could this be an overflow issue? Can you provide example input which fails? — Scheff's Cat, Jan 08 '20 at 06:45
Does the input have a limited range? (Consider what happens when all numbers are `INT_MAX / 2`.) — molbdnilo, Jan 08 '20 at 06:47
@Scheff Input -> 256741038, 623958417, 467905213, 714532089, 938071625 — ANIKET LAVKUSH VISHWAKARMA 19B, Jan 08 '20 at 06:53
@Scheff yes sorting would be a smarter way... but now I'm just curious as to why it is failing — ANIKET LAVKUSH VISHWAKARMA 19B, Jan 08 '20 at 06:55
Aha.: 623958417 + 467905213 + 714532089 + 938071625 = 2744467344 (computed on my Windows 7 calculator). Please, note that this the unsigned addition where the most significant bit (bit 31) is set. For a signed 32 bit integer, this would result into a negative number. (Actually, overflow is Undefined Behavior for signed integers in C++.) — Scheff's Cat, Jan 08 '20 at 07:04
Does this answer your question? [C++ integer overflow](https://stackoverflow.com/questions/29235436/c-integer-overflow) — Mahmoud Hendi, Jan 09 '20 at 07:48

H S · Answer 1 · 2020-01-08T08:03:52.660

Your code suffers from Integer Overflow. Integer in most modern computers range from -2,147,483,648 to 2,147,483,647. Since you have mentioned in comments that your input can go from 1 to 10^9 and size of array is 5, Maximum sum can be 5 * 10^9 , which is indeed greater than 2,147,483,647. You simply need a datatype which can hold larger values, use :

long long
std::int64_t

Please note that even unsigned int won't do the job because it's 4,294,967,295 < 5 * 10^9. Another thing is difference between

A. int a = 2,147,483,647 ; int b = 2,147,483,647 ; long long k = a + b .Now, since a and b are integer, thus overflow would happen before assigning it back to long long because integer addition aka 32 bit addition will happen.

B. long long a = 2,147,483,647; long long b = 2,147,483,647; long long k = a + b. Now, Overflow won't happen because addition will be performed over long long since a and b are long long and 64 bit addition will happen

Code would look like this:

long long list[5]; //See int is now long long
long long minisum, maxsum;

for (int i=0; i<5; i++) //i can be int because it's size of list i.e 5
{
    cin>>list[i];
}

minisum=minimini(list);
maxsum=maxa(list);

cout<<minisum<<" "<<maxsum;

MLKu · Answer 2 · 2020-01-09T00:58:05.943

the int type has its range:

int: -2,147,483,648 to 2,147,483,647

if use type long long int, would be better.

long long int: -(2^63) to (2^63)-1

below are my test code refer to LernerCpp's comments to append typedef statement:

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

typedef long long int INT64;

INT64 minimini(INT64 list[]){
    INT64 minisum=0;
    INT64 taker;
    INT64 a=max({list[0],list[1],list[2],list[3],list[4]});
    for (int i=0; i<5; i++){
        taker=list[i];
        if(taker!=a){
            minisum=minisum+taker;
        }
    }
return minisum;
}
INT64 maxa(INT64 list[]){
    INT64 maxsum=0;
    INT64 taker;
    INT64 a=min({list[0],list[1],list[2],list[3],list[4]});
    for (int i=0; i<5; i++){
        taker=list[i];
        if(taker!=a){
            maxsum=maxsum+taker;
            cout<<"maxsum >>"<<maxsum<<endl;
            cout<<"a="<<a<<endl;
        }
    }
return maxsum;
}
int main(){
    INT64 list[5];
    INT64 minisum, maxsum;
    // int: -2,147,483,648 to 2,147,483,647
    // long long int:   -(2^63) to (2^63)-1
    for (int i=0; i<5; i++){
        std::string tmp;
        char* pEnd=0;
        printf("enter number %d:\n",i);
        cin>>tmp;
        list[i]=strtoll(tmp.c_str(),&pEnd,10);
        printf("number %d: %lld\n",i,list[i]);
    }

    printf("the list array are: [%lld,%lld,%lld,%lld,%lld,]\n",list[0],list[1],list[2],list[3],list[4]);

    minisum=minimini(list);
    maxsum=maxa(list);

    cout<<minisum<<" "<<maxsum;


    return 0;
}

Live Demo on coliru

and the result:

C:\Users\s41167\Documents\mingw-w64>test_maximum.exe
enter number 0:
10000000000
number 0: 10000000000
enter number 1:
-10000000000
number 1: -10000000000
enter number 2:
20000000000
number 2: 20000000000
enter number 3:
-20000000000
number 3: -20000000000
enter number 4:
30000000000
number 4: 30000000000
the list array are: [10000000000,-10000000000,20000000000,-20000000000,300000000
00,]
maxsum >>10000000000
a=-20000000000
maxsum >>0
a=-20000000000
maxsum >>20000000000
a=-20000000000
maxsum >>50000000000
a=-20000000000
0 50000000000
C:\Users\s41167\Documents\mingw-w64>

and ANIKET LAVKUSH VISHWAKARMA 19B's input:

C:\Users\s41167\Documents\mingw-w64>test_maximum.exe
enter number 0:
256741038
number 0: 256741038
enter number 1:
623958417
number 1: 623958417
enter number 2:
467905213
number 2: 467905213
enter number 3:
714532089
number 3: 714532089
enter number 4:
938071625
number 4: 938071625
the list array are: [256741038,623958417,467905213,714532089,938071625,]
maxsum >>623958417
a=256741038
maxsum >>1091863630
a=256741038
maxsum >>1806395719
a=256741038
maxsum >>2744467344
a=256741038
2063136757 2744467344
C:\Users\s41167\Documents\mingw-w64>

Instead of typing the long *long long int*, you count have used a type aliase! — LernerCpp, Jan 08 '20 at 08:12

Verthais · Answer 3 · 2020-01-08T10:37:04.063

While it's true that the int range is an issue what's hard for me to fathom is why you wont use any of new C++ features like:

#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>

using lli_t = long long int;

int main(){
    std::array<int,5> list;

    for (int i=0; i<list.size(); i++){
        std::cin>>list[i];
    }

    std::sort(std::begin(list), std::end(list));

    auto minsum = std::accumulate(std::begin(list), std::begin(list)+4, static_cast<lli_t>(0));
    auto maxsum = std::accumulate(std::begin(list)+1, std::end(list), static_cast<lli_t>(0));

    std::cout << minsum << " " << maxsum;

    return 0;
}

score 0 · Answer 4 · edited Jan 08 '20 at 07:28

0

The integer data type can only hold values from -2,147,483,647 to 2,147,483,647 [1]. An easy way to fix this is to change all the int declarations to float or double or long data types.

[1] https://www.ibm.com/support/knowledgecenter/en/SSGU8G_12.1.0/com.ibm.sqlr.doc/ids_sqr_122.htm

edited Jan 08 '20 at 07:28

Alan Birtles

32,622
4
31
60

answered Jan 08 '20 at 06:50

DhyeyL

25
5

`long` has 32 bits on certain platforms as well (e.g. on my Windows/VS2013). To be on the safe side, I would prefer `long long` or `std::int64_t`. – Scheff's Cat Jan 08 '20 at 06:56
Why in the world did you link to an SQL reference? – Blastfurnace Jan 08 '20 at 07:05
@Scheff using long long or std::int64_t both still give the same incorrect output for those test cases – ANIKET LAVKUSH VISHWAKARMA 19B Jan 08 '20 at 07:06
`float` has 23 bits mantissa. Hence, it cannot store 32 bit integers precisely. I wouldn't consider this as proper alternative as well. – Scheff's Cat Jan 08 '20 at 07:07
@ANIKETLAVKUSHVISHWAKARMA19B The trick is to convert (cast) the _arguments_ of the addition to `long long`. Otherwise, you get a 32 bit addition (with overflow issue) stored into a 64 bit var. – Scheff's Cat Jan 08 '20 at 07:08
@Scheff yes thank you, it works now that the overflow is solved by converting the argument to long long – ANIKET LAVKUSH VISHWAKARMA 19B Jan 08 '20 at 07:43
@Blastfurnace man it was the first link on google is it really that deep – DhyeyL Jan 08 '20 at 10:59
Your link is wrong for C++. The range for a 32-bit `signed int` is -2,147,483,648 to 2,147,483,647 – Blastfurnace Jan 08 '20 at 23:25

I have to find the maximum sum of 4 numbers from an array of 5. My code fails for bigger numbers

4 Answers4