Here’s a fun algorithmic challenge for you.
Given a list of integers, write a function to find the total number of complete pairs contained in the list.
For example: for the input
[3, 1, 2, 3, 1, 2],
the return value should be
3
because there are 2
1s, 2
2s and 2
3s.
4 has no matching pair.
The image above gives a visual representation of the problem.
Have a go now at the challenge. Here’s a function stub and some assertions to get you started. If you are not familiar with
assert in Python, these are just basic tests which will raise errors if they are incorrect. If you run you code and get no
AssertionErrors, it means all the tests passed and your code is correct.
Counting Pairs Python Coding Challenge
def count_pairs(items): pass items = [] assert count_pairs(items) == 0 items = [1] assert count_pairs(items) == 0 items = [3, 1, 2, 3, 1, 2] assert count_pairs(items) == 3 items = [3, 1, 2, 3, 1, 2, 4] assert count_pairs(items) == 3 items = [4, 3, 1, 2, 3, 1, 2, 4] assert count_pairs(items) == 4 items = [9, 9, 9, 9, 9, 9, 9, 9, 9] assert count_pairs(items) == 4
Counting Pairs Python Coding Challenge
How did you get on?
Click below to see my initial solution to this problem. Then I will show you some alternatives and refinements.
def count_pairs(items): # Create a dictionary to store the frequencies of items frequencies = {} # Iterate through items and store frequencies of each item for item in items: if item in frequencies: frequencies[item] += 1 else: frequencies[item] = 1 # Initialise result num_pairs = 0 # Calculate the number of complete pairs for each item and update result for key in frequencies: num_pairs += frequencies[key] // 2 return num_pairs
The approach in the above solution was to build a dictionary of frequencies for each unique item in the list, and then to use integer division (
//) by
2 to then find how many complete pairs there were for each key. This works because, for example,
5 // 2 = 2 4 // 2 = 2
Python Counter
The creation of the
frequencies dictionary in the above solution can be simplified by the of of a
Counter from the Python
collections module. This is handy little tool that it is well worth knowing about. You will need to import it to make use of it.
from collections import Counter def count_pairs(items): frequencies = Counter(items) num_pairs = 0 for key in frequencies: num_pairs += frequencies[key] // 2 return num_pairs
Solving the Python Counting Pairs Programming Challenge using Sets
Another approach you can use for this problem is the make use of sets. You can learn more about Python sets here. The basic idea is that a set is created from the list of items, which contains only a singe instance of each value in the list. It is then a simple matter to count the number of items corresponding to each set elements within the original list.
def count_pairs(items): num_pairs = 0 for item in set(items): num_pairs += items.count(item) // 2 return num_pairs
For a super-succinct verions of the above soluiton, you can do this:
def count_pairs(items): return sum([items.count(i) // 2 for i in set(items)])
There it is folks. I hope you had a good attempt at this Python programming challenge, and wheter you managed to solve it yourself or not, you learned something on the way.
Happy computing.