Long long int Overflow

Question

Ниже приведен мой код для добавления 4-х элементов вектора arr и последующей печати минимальной суммы и максимальной суммы. Это ниже мой код. Хотя после использования длинного знака без знака, диапазон которого составляет от 0 до 18,446,744,073,709,551,615 , если быть точным. Я получаю ответ о переполнении целого числа, когда контрольный пример 256741038 623958417 467905213 714532089 938071625 . По мне, ответ должен быть в пределах ULL. Пожалуйста, помогите мне лучше понять причину.

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];
}

Answer 1

vector<int> A; - вектор целых чисел. Когда вы A.push_back(ans);, ans преобразуется в int, что приводит к переполнению.

Простое изменение объявления A на vector<unsigned long long int> A; устраняет проблему

Answer 2

Есть несколько «проблем» с этим кодом, я бы посоветовал внести несколько изменений:

1. Передача вектора по значению довольно дорогая, лучше передать по ссылке, и поскольку вы не изменяете входной вектор, сделайте его постоянным. void miniMaxSum(const std::vector<int>& arr)
2. два уровня циклов - логарифмическая сложность (N ^ 2), вы можете вычислить общую сумму arr, а затем снова go над arr и вычесть каждый элемент из общего сумма, чтобы получить ваш ответ.
3. , так как вас интересуют только min_sum и max_sum, вы можете избежать дорогостоящей сортировки в конце.
4. , поскольку ваши входные данные int s, вы бы не используйте unsigned int для хранения результатов, так что ваш код будет также работать для отрицательных целых чисел в качестве входных данных.
5. не используйте жесткий код / ​​предполагается, что ваш входной вектор всегда содержит 5 элементов, вместо этого используйте arr.size().

Ниже приведен модифицированный код со сложностью Log (N).

#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;
}