Using partial_sum() with long long values-CodePudding

I am solving a problem for which, I need to calculate the prefix and suffix sum values. When I do it this way:

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        long n=size(nums);
        vector<long long> left(n,0ll), right(n,0ll);
        
        partial_sum(begin(nums), end(nums), begin(left));
        partial_sum(rbegin(nums), rend(nums), rbegin(right));
        
        return 0;
    }
};

This works fine for smaller input values, but when the input is very large, I get an error:

Line 258: Char 43: runtime error: signed integer overflow: 2147453785 36049 cannot be represented in type 'int' (stl_numeric.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c /9/bits/stl_numeric.h:267:43

However, the traditional for-loop works just fine for all the inputs, including the very large ones:

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        long n=size(nums);
        vector<long long> left(n,0ll), right(n,0ll);
        
        left[0]=nums[0];
        for(int i=1; i<n; i  ) {
            left[i]=left[i-1] nums[i];
        }
        
        right[n-1]=nums[n-1];
        for(int i=n-2; i>=0; i--) {
            right[i]=right[i 1] nums[i];
        }

        return 0;
    }
};

What am I missing about the usage of partial_sum()?

CodePudding user response：

This error is caused by integer overflow when the std::partial_sum function is used to calculate the prefix and suffix sums of the nums vector. The std::partial_sum function uses the operator to accumulate the sum of the values in the vector, and if the sum exceeds the maximum value that can be represented by the int type, integer overflow occurs and undefined behavior is triggered.

To fix this error, you can use the std::int64_t type to store the sum values, instead of the int type. This is a signed 64-bit integer type that can represent larger values and prevent integer overflow.

Here is an example of how you can modify your code to use std::int64_t:

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        // Use std::int64_t to store the sum values
        long n=size(nums);
        vector<std::int64_t> left(n,0ll), right(n,0ll);

        // Use std::partial_sum to calculate the prefix and suffix sums
        partial_sum(begin(nums), end(nums), begin(left));
        partial_sum(rbegin(nums), rend(nums), rbegin(right));

        return 0;
    }
};

This should fix the integer overflow error and allow your code to handle larger input values without triggering undefined behavior. Note that you also need to change the declaration of the n variable to use std::int64_t, to match the type of the left and right vectors.

CodePudding user response：

std::partial_sum() is defined such that the accumulator type is that as the type of the input range element. This is also true for an overload that takes a custom binary operation.

If you really want to use std::partial_sum(), you could either copy an input range into std::vector<long long> or transform it on-fly using boost::transform_iterator:

std::vector<int> in(5, INT_MAX);
std::vector<long long> out(in.size());

auto cast_to_long_long = [](int v){ return static_cast<long long>(v); };
auto first = boost::make_transform_iterator(in.begin(), cast_to_long_long);
auto last  = boost::make_transform_iterator(in.end(),   cast_to_long_long);

std::partial_sum(first, last, out.begin());

Demo