CSES problem,apple division

CSES - Apple Division this is link to problem.
somebody please help me understand this code here,please!

#include <bits/stdc++.h>
#define lli long long int
#define li long int
#define ld long double
using namespace std;
const lli mod = 1e9 + 7;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli n, total=0, ans=INT_MAX;
cin >> n;
li arr[n];
for(lli i = 0; i < n; i++) {
cin >> arr[i];
total += arr[i];
}
for(lli i = 0; i < 1<<n; i++) {
lli s = 0;
for(lli j = 0; j < n; j++) {
if(i & 1<<j) s += arr[j];
}
lli curr = abs((total-s)-s);
ans = min(ans, curr);
}
cout << ans;
return 0;
}

1 Like

It literally just tries all possible subsets and takes the minimum absolute difference (note that the second group is, by default, anything that isn’t in the first group).

3 Likes

thanku so much for taking time, i m just not getting the line(i & 1<<j) why is it checking the jth bit of i.

6 Likes

it was amazing, really amazing thing i learnt today ! thanku so much !

learnt a new thing thank you.
but i have only one query
this solution is possible when n<=32 right? because if n>32 it can’t be represented in the bit representation right? coorect me if i am wrong
i am trying to learn bit manipulation

Mostly correct (although you could use 64-bit long long too - that’s the real upper limit). And looping all other masks would have other problems too with that many values, 2^{32} or 2^{64} operations would definitely TLE.

2 Likes

Please explain that solution to me.

ohh okay thank you for the help.

you can also use a back tracking approach for this problem

you can use bits to solve this problem by looping over all the possible combinations as described in other replies but here i found a recursive and dynamic programming solution
link

I am solving Apple division CSES,

n < 21 i.e. TC - 2e7 which means the solution should get accepted, but it is not I am getting TLE!
Also, cannot use DP cause, weight of apple is 10^9, idk how to solve this!

Can you help?

Edit - I am using Python.