Chris - 8 months ago 40

Python Question

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`

) and two non-empty,`1 < m < 1000000`

zero-indexed arraysand`A`

of`B`

integers,`n`

,`a0`

, ... ,`a1`

and`an−1`

,`b0`

, ... ,`b1`

respectively (`bn−1`

,`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

arrayequals the sum of elements in array`A`

after the swap. By`B`

swap operation we mean picking one element from arrayand one`A`

element from arrayand exchanging them.`B`

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.

Source (Stackoverflow)