Swap The Elements (A problem on counting elements)

Swap The Elements

Problem

Problem: 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, … , a(n-1) and b0, b1, ... , b(n-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.

Example

x = [3, 4, 2, 1, 0]

y = [3, 1, 4, 2, 2]

print(sum(x))

print(sum(y))

Out:

10

12

# Swapping '2 from y' with '1 from x'.

x = [3, 4, 2, 2, 0]

y = [3, 1, 4, 2, 1]

print(sum(x))

print(sum(y))

Out:

11

11

# Also, on swapping '3 from y' and '2 from x'.

x = [3, 4, 3, 1, 0]

y = [2, 1, 4, 2, 2]

print(sum(x))

print(sum(y))

Out:

11

11

# Also, on swapping '4 from y' and '3 from x'.

x = [4, 4, 2, 1, 0]

y = [3, 1, 3, 2, 2]

print(sum(x))

print(sum(y))

Out:

11

11

Hint

After the swap operation, the two sums (sum_a and sum_b) should become equal.

And if initially, sum_b - sum_a = d

This is total change we want.

Now, since sum_b + sum_a = Constant (before and after the swap), we can then say:

Half of this change (viz. d/2) will come from side 'b' and half (viz. d/2) will come from side 'a'.

(This is equivalent to saying side 'a' and side 'b' will meet the halfway.)

Since side 'b' is higher, we would have to swap a value B[i] with B[i] - d/2

Now for this, we will loop through side 'b' to find that B[i] for which 'B[i] - d/2' is in side 'a'.

Brute Force Solution

Solution O(n^2): The simplest method is to swap every pair of elements and calculate the totals. Using that approach gives us O(n^3) time complexity. A better approach is to calculate the sums of elements at the beginning, and check only how the totals change during the swap operation.

Linear Time Complexity Solution

Solution O(n + m): The best approach is to count the elements of array A and calculate the difference d between the sums of the elements of array A and B.

For every element of array B, we assume that we will swap it with some element from array A. The difference d tells us the value from array A that we are interested in swapping, because only one value will cause the two totals to be equal. The occurrence of this value can be found in constant time from the array used for counting.

Code

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

Note: counting() is:
def counting(A, m):
  n = len(A)
  count = [0] * (m + 1)
  for k in xrange(n):
    count[A[k]] += 1
  return count

'counting()' can be replaced with 'Counter':
>>> l = ['A', 'B', 'C']

>>> from collections import Counter
>>> Counter(l)
Counter({'A': 1, 'B': 1, 'C': 1})
>>>