i have an algorithm but i don’t know how or why does it work closed-call

A = {2}, B = {1,3} Return value: {2,3}

Let’s first pull this example apart.

before the exchange, A’s total amount of chocolate is 2, and B has 4 (1+3).

Then, an exchange happens: A transfers their 2-sized slab over (subtract 2 from A’s and add 2 to B’s, so they are now at {0, 6}, and then B transfers their 3-sized slab, so subtract 3 from B and add 3 to A: {3, 3}, which is in balance, therefore {2, 3} is the right answer.

Clearly then, one rather inefficient strategy is to simulate the exchange of every single slab A has vs. every single last slab B has, and return the moment we just so happen to stumble upon an exchange that results in the end result being balanced.

And that’s exactly what your algorithm does: It exchanges every possible slab for both A and B until it finds a hit:

int sum1 = arraySum(arr);

sum1 is the size of A’s chocolate hoard, pre-exchange. In our example, 2.

int sum2 = arraySum(arr2);

sum2 is the size of B’s chocolate hoard, pre-exchange. In our example, 4.

int sub = sum1 - sum2;

The difference between how much chocolate A has vs. how much B has (-2 means: B has 2 more chocolate than A). This means that half this number needs to ‘flow’ from A to B for balance (in this example, the desired flow is -1: a net of 1 chocolate needs to go from B to A, then we have balance). The ‘half’ part comes later, though – it would have been easier to read and more efficient to do the /2 here.

for(int i = 0; i<arr.length; i++){ for(int j = 0; j < arr2.length; j++){

A double nested loop; i/j will cover every potential exchange. This grows FAST. If A has 10 slabs of chocolate and B has 20 slabs, then there are 200 possible exchanges, and this construct will consider them all.

if(sub/2 == arr[i] - arr2[j]){

We have selected one of A’s slabs to give away to B (the i-th slab), and one of B’s slabs to give to A (the j-th slab). So, let’s get the size of A’s i-th slab (arr[i]) and the size of B’s j-th slab (arr2[j]), and check the difference. In our example (remember, it was A={2}, B={1,3} to start), the right exchange is i=0 (A’s 2-sized slab) and j=1 (B’s 3-sized slab). 2-3 is -1, as in, this is a net ‘flow’ of chocolate where 1 flows from B to A (if it was positive, it would be from A to B). It’s what we wanted, and here the /2 shows up. Our sub value was -2, it is divided by 2, so that makes for -1, and that is equal to arr[i] - arr2[j]. If this if block succeeds, we found an exchange that’ll work: The code then sets the values of result, otherwise, do nothing, and notably, keep going, even though we already have an answer – that’s just this particular algorithm being bad.

Then, result is returned, incidentally that also means the algorithm returns “A should exchange their first slab with B’s first slab” if there is no exchange possible, i.e. the code just straight up is wrong if no exchange is possible. I guess the exercise does not care that your code fails by giving a wrong answer if no exchange is possible.

There are more efficient ways of doing this, but they’d involve writing more code. For example, you can sort A’s slabs and B’s slabs by size first (that’s 2 O(nlogn) operations), then loop through A’s slabs (O(n)), and for each slab calculate how large B’s slab would have to be to make the exchange perfect. If it’s negative, continue; immediately to A’s next slab. Otherwise, use binary search to check if B has a slab of this desired size. binary search is O(logn). If yes, return the right result, if not, move on to A’s next slab.

That’s 2*O(n logn) (O(n) * O(log n)), which boils down to O(nlogn), whereas your algorithm is O(n^2).

That means, if you graph the performance of these 2 algorithms by graphing ‘# of slabs that the 2 friends have’ against ‘how much time it takes for the algorithm to finish calculating the result’, your algorithm looks like y=x^2, and the above looks like y=x * log(x), and therefore ‘my’ algorithm will eventually be faster, and significantly so, given large enough inputs.

Usually with algorithm exercises like this, the point is to find the most efficient algorithm, and correct code that nevertheless takes too long for the (generally quite large) test inputs is still deemed a failure.

That may not be the case here, but, it seemed pertinent to tell you about a more efficient algorithm.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top