python: algorithm for swapping elements between two arrays

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 (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

score 3 · Accepted Answer · 2016-10-28 00:44:12Z

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.

ok,I got the concept. Knowing the difference between arrays B and A, we check if each element of B could be replaced by a number lower by difference/2 (let's call it x), so that the sums of the arrays get equal. Fist part of the loop checks if x is in the range of interest (between 0 and m) and the second part checks if x exist in the A, if it exists there (count>0) then the swap is possible.

YiFei · Accepted Answer · 2016-10-27 03:36:29Z

I'm not sure I get your idea correctly. Here's my understanding:

def counting(A, m):
   n = len(A)
   count = [0] * (m + 1)
   for k in xrange(n):
       count[A[k]] += 1
   return count # this essentially build a counter


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) # get the dict
    for i in xrange(n):
        if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
        # the first two conditions are to verify that B[i]-d exists as a key (index) in counter.
        # then check if there actually exists the value.
        # if count > 0, then you can swap the two to get same sum
            return True
    return False

Or rewriting to get:

def counting(A, m):
   count = collections.Counter()
   for i in A:
       count[i] += 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) # get the dict
    for i in B:
        if count[i-d]:
            return True
    return False

But in any case, this piece of code just check the solution existence with only single swap, be sure to check if that's what you wanted.

Collectives™ on Stack Overflow

python: algorithm for swapping elements between two arrays

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related