Chris - 1 month ago 6
Python Question

# python: algorithm for swapping elements between two arrays

I am analyzing counting example in python presented by Codility

I don't understand the logic used in the last loop (5 last rows) of this algorithm.

The problem:

You are given an integer
`m`
(
`1 < m < 1000000`
) and two non-empty,
zero-indexed arrays
`A`
and
`B`
of
`n`
integers,
`a0`
,
`a1`
, ... ,
`an−1`
and
`b0`
,
`b1`
, ... ,
`bn−1`
respectively (
`0 < ai`
,
`bi < m`
).
The goal is to check whether there is a swap operation which can be
performed on these arrays in such a way that the sum of elements in
array
`A`
equals the sum of elements in array
`B`
after the swap. By
swap operation we mean picking one element from array
`A`
and one
element from array
`B`
and exchanging them.

The solution:

``````def counting(A, m):
n = len(A)
count = [0] * (m + 1)
for k in xrange(n):
count[A[k]] += 1
return count

def fast_solution(A, B, m):
n = len(A)
sum_a = sum(A)
sum_b = sum(B)
d = sum_b - sum_a
if d % 2 == 1:
return False
d //= 2
count = counting(A, m)
for i in xrange(n):
if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
return True
return False
``````

What I would recommend you is read again the explanations given in the exercise. It already explains what how the algorithm works. However, if you still have problems with it, then take a piece of paper, and some very simple example arrays and go through the solution step by step.

For example, let `A = [6, 6, 1, 2, 3]` and `B = [1, 5, 3, 2, 1]`.

Now let's go through the algorithm.

I assume you understand how this method works:

``````def counting(A, m):
n = len(A)
count = [0] * (m + 1)
for k in xrange(n):
count[A[k]] += 1
return count
``````

It just returns a list with counts as explained in the exercise. For list A and m = 10 it will return:

``````[0, 1, 1, 1, 0, 0, 2, 0, 0, 0, 0]
``````

Then we go through the main method `fast_solution(A, B, m)`:

`n = 11` (this will be used in the loop)

The sum of A equals `18` and the sum of B equals `12`.

The difference `d` is `-6` (sum_b - sum_a), it is even. Note that if difference is odd, then no swap is available and the result is False.

Then `d` is divided by `2`. It becomes `-3`.

For A we get count `[0, 1, 1, 1, 0, 0, 2, 0, 0, 0, 0]` (as already mentioned before).

Then we just iterate though the list B using `xrange` and check the conditions (The loop goes from 0 and up to but not including 11). Let's check it step by step:

`i = 0`, `B[0] - (-3)` is `1 + 3 = 4`. 4 is greater than or equal to 0 and less than or equal to 10 (remember, we have chosen `m` to be `10`). However, `count[4]` is 0 and it's not greater than 0 (Note the list `count` starts from index `0`). The condition fails, we go further.

`i = 1`, `B[1] - (-3)` is `5 + 3 = 8`. 8 is greater than or equal to 0 and less than or equal to 10. However, `count[8]` is 0 and the condition fails.

`i = 2`, `B[2] - (-3)` is `3 + 3 = 6`. 6 is greater than 0 and less than 10. Also `count[6]` is 2 and it is greater than 0. So we found the number. The loop stops, True is returned. It means that there is such a number in B which can be swapped with a number in A, so that sum of A becomes equal to the sum of B. Indeed, if we swap 6 in A with 3 in B, then their sum become equal to 15.

Hope this helps.