Chris 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.

Can anybody help please?

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

Answer

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.

Comments