1

So, I was doing a question that asked us to divide an array into two parts such that the difference between the sum of elements of both of the parts shall be minimum. Say A = [3 2 7 4 1]. So, minimum difference is generated when [2 3 4] and [7 1] are the two parts, i.e. difference = (2+3+4)-(7+1) = 1.

My approach was pretty naive, which basically computed all different subsets of the given array, and calculate the absolute difference with its complementary array, and report the minimum of these values.

When I used int my program it gave the correct answers for all but two test cases. In these test cases, the inputs were exceeding the limits of int. So, I changed it to long long, but this gave very weird results. It even started giving wrong results for the previously correct results.

CORRECT OUTPUT GIVING CODE (using int):

#include <bits/stdc++.h>

typedef long long ll;
 
using namespace std;
 
 
int min_diff = INT_MAX;
 
void subsetGen(vector <int> &curr,vector <int> &v, int n, int index, int sum)
{
    if (!curr.empty())
    {
        int sum_1 = accumulate(curr.begin(), curr.end(), 0);
        int diff = abs(2*sum_1 - sum);
        min_diff = (diff<min_diff) ? diff : min_diff;

    }
    for (int i = index; i < v.size(); i++)
    {
        curr.push_back(v[i]);
 
        subsetGen (curr, v, n, i+1, sum);
 
        curr.pop_back(); // Backtracking
    }
    return;   
}
 
int main()
{
    int n, sum = 0;
    cin >> n;
    vector <int> v (n, 0);
    for (int i=0; i<n; i++)
    {
        cin >> v[i];
        sum += v[i];
    }
    vector <int> curr;
    subsetGen(curr,v,n,0,sum);
    cout << min_diff;
    return 0;
}

INCORRECT OUTPUT GIVING CODE (using long long):

#include <bits/stdc++.h>

typedef long long ll;
 
using namespace std;
 
 
ll min_diff = LLONG_MAX;
 
void subsetGen(vector <ll> &curr,vector <ll> &v, int n, int index, ll sum)
{
    if (!curr.empty())
    {
        ll sum_1 = accumulate(curr.begin(), curr.end(), 0);
        ll diff = abs(2*sum_1 - sum);
        min_diff = (diff<min_diff) ? diff : min_diff;

    }
    for (int i = index; i < v.size(); i++)
    {
        curr.push_back(v[i]);
 
        subsetGen (curr, v, n, i+1, sum);
 
        curr.pop_back(); // Backtracking
    }
    return;   
}
 
int main()
{
    int n;
    ll sum = 0;
    cin >> n;
    vector <ll> v (n, 0);
    for (int i=0; i<n; i++)
    {
        cin >> v[i];
        sum += v[i];
    }
    vector <ll> curr;
    subsetGen(curr,v,n,0,sum);
    cout << min_diff;
    return 0;
}

This was the Input I was checking for:

20
452747515 202201476 845758891 733204504 327861300 368456549 64252070 494676885 21095634 611030397 913689714 849191653 173901982 954566440 40404105 228316310 210730656 631709598 847867437 85805975

The correct answer is: 4881 (which the program using int gave) But using long long is giving me: 4762526359 (which is the wrong answer).

I tested these code in online compilers to see if this was a problem with only my system, but encountered the same problem.

Vedanta Mohapatra
  • 451
  • 2
  • 16
  • 3
    It's possible that this is a consequence of [this common pitfall](https://en.cppreference.com/w/cpp/algorithm/accumulate#Common_mistakes) with `std::accumulate`. You might want to do `accumulate(curr.begin(), curr.end(), 0LL)` for the long long version. – Nathan Pierson Dec 26 '21 at 16:40
  • Thanks, this worked!. Is this problem with other common STL functions in C++? – Vedanta Mohapatra Dec 26 '21 at 16:44
  • `std::reduce` And omit the third argument. – sweenish Dec 26 '21 at 16:45
  • See [Why should I not #include ?](https://stackoverflow.com/q/31816095) and [Why using namespace std is bad practice](https://stackoverflow.com/questions/1452721). – prapin Dec 26 '21 at 21:42

0 Answers0