Codility - Lesson 4 Counting elements

Source Link:
https://codility.com/programmers/lessons/4-counting_elements/

Some Notes:



Notice that we do not place elements directly into a cell; rather, we simply count their occurrences. It is important that the array in which we count elements is sufficiently large. If we know that all the elements are in the set {0, 1, . . . ,m}, then the array used for counting should be of size m + 1. 

Counting the number of negative integers can be done in two ways.
In the second method, we simply create a second array for counting negative numbers. 

4.1. Exercise

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, . . . , an−1 and b0, b1, . . . , bn−1 respectively.

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.  

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.  

The occurrence of this value can be found in constant time from the array used for counting. 

4.3: Swap the elements — O(n + m).
1 def fast_solution(A, B, m):
2 n = len(A)
3 sum_a = sum(A)
4 sum_b = sum(B)
5 d = sum_b - sum_a
6 if d % 2 == 1:
7 return False
8 d //= 2
9 count = counting(A, m)
10 for i in xrange(n):
11 if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
12 return True
13 return False