CountingElements solution

Question

I am trying to understand a problem and the solution provided. But not able to grasp it completely https://codility.com/media/train/2-CountingElements.pdf

You are given an integer m (1 <= m <= 1 000 000) 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.

And Solution goes like this

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

(0 <= ai , bi <= m) Does this mean (0<=ai<=bi<=m)? Is it how this equation is represented? I think this should be the case given the solution.

what is the logic behind this section?

 if d % 2 == 1:
 return False
 d //= 2

Thanks for your help

Answer 1

what is the logic behind this section?

if d % 2 == 1: return False d //= 2

The logic is very simple.

Explanation

This can easily be done by following simple few steps:

Sum 1 = sum of (a0, a1, . . . , an−1)

time taken O(N)

Sum 2 = sum of (b0, b1, . . . , bn−1)

time taken O(N)

Suppose the solution pair is (ai,bi). This means that: Sum 2 + ai - bi = Sum 1 + bi - ai, Which means that:

ai - bi = (Sum 1 - Sum 2)/2  // equation 1

The above equation indicates that the difference of sums must be divisible by 2 for solution to exist as the arrays are made of integers.

Looks like we can use binary search . Now sort one of the arrays(say A) to prepare it for binary search. Time taken O(NlogN). Now traverse the array B and for each bi, the value of ai can be found from above equation. So compute ai and check if it exist in array A using binary search. This will also take O(NlogN), since we apply binary search at most N times in worst case.

Alternate solution

Another solution could be making use of hash table data structure which takes O(N) time but the space complexity would be O(N) .