CODEWITHSUNDEEP
c++overflow
DrkEthics
DrkEthics

Reputation: 3

Long long int Overflow

This below is my code for adding 4 elements of vector arr and then printing the min-sum and the max-sum. This below is my code. Though after using unsigned long long of which the range is 0 to 18,446,744,073,709,551,615 to be precise. I am getting an integer overflow answer when the test case is 256741038 623958417 467905213 714532089 938071625. According to me, the answer should be in the limit of u-l-l. Please help me to better understand the cause.

void miniMaxSum(vector<int> arr) {
vector<int> A;
for(int i=0;i<5;i++){
    unsigned long long int ans=0;
    for(int j=0;j<5;j++){
        if(i==j)    continue;
        else    ans+=arr[j];
    }
    A.push_back(ans);
}
sort(A.begin(), A.end());
cout<<A[0]<<" "<<A[4];
}

Upvotes: 0

Views: 458

Answers (2)

Tiger Yu
Tiger Yu

Reputation: 764

There is a couple of "issues" with this code, I'd suggest to make a few changes:

  1. passing vector by value is quite expensive, it's better to pass by reference, and since your don't mutate the input vector, so make it const. void miniMaxSum(const std::vector<int>& arr)
  2. the two level of loops is Log(N^2) complexity, you can calculate total sum of arr, and then go over arr again and subtract each element from the total sum to get your answer.
  3. since you are only interested in min_sum and max_sum, you can avoid the expensive sorting at the end.
  4. since your inputs are ints, you'd not use unsigned int to hold results, so that your code will also work for negative integers as input.
  5. do not hard code/assume your input vector always contains 5 elements, use arr.size() instead.

The following is the modified code, which is in Log(N) complexity.

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

void miniMaxSum(const std::vector<int>& arr) {
    vector<int64_t> A;
    int64_t sum = std::accumulate(arr.begin(), arr.end(), 0ull);
    int64_t min_sum = LLONG_MAX;
    int64_t max_sum = LLONG_MIN;
    for(int i=0;i<arr.size();i++){
        int64_t v = sum - arr[i];
        if (v < min_sum) min_sum = v;
        if (v > max_sum) max_sum = v;
    }
    cout<<min_sum<<" "<<max_sum;
}

int main() {
    vector<int> a{256741038, 623958417, 467905213, 714532089, 938071625};
    miniMaxSum(a);
    return 0;
}

Upvotes: 0

sparik
sparik

Reputation: 1201

vector<int> A; is a vector of ints. When you A.push_back(ans);, ans gets converted to int, which results in overflow.

Just changing the declaration of A to vector<unsigned long long int> A; fixes the issue

Upvotes: 3

Related Questions