Codility Counting Lesson

Question

I'm studying Codility Counting Lesson (https://codility.com/media/train/2-CountingElements.pdf) and I need help to understand the fastest solution.

I am wondering why the difference is divided by 2 in line 8 d //= 2? Shouldn't the difference be sufficient to find the elements that we can swap between the arrays?

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

A swap between A[i] and B[j] adds B[j]-A[i] to sum(A) and subtracts the same value from sum(B); therefore it affects the difference of the sums by twice B[j]-A[i].

As a consequence, it's correct to halve the original difference (after checking it's even -- if it's odd no swap will work!-) to form the target for a possible swap.

Note also that the counting function they provide is not optimal modern Python -- to avoid reinventing the specific wheel of "counting items", see https://docs.python.org/2/library/collections.html#collections.Counter for Python 2, or https://docs.python.org/3/library/collections.html#collections.Counter for Python 3.

Answer 2

Let Ea = a0 + a1 + .. + a(n-1). Let Eb = b0 + b1 + .. + b(n-1). Then swapping element ai and bj would cause the following effects on those sums: Ea - ai + bj, Eb + ai - bj. According to the Problem description, then those sums should be equal, so Ea - ai + bj = Eb + ai - bj Let's designate d = bj - ai. Then we have the following equality: Ea + d = Eb - d which gives us 2d = Eb - Ea or d = (Eb - Ea)/2. For the case when (Eb - Ea) is odd please see the comment from Alex Martelli

The only thing left is to find such bj and ai so that bj - ai = d.