Python Algorithm Challenge - Counting Pairs

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.

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.

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}

Join our mailing list

Join our mailing list to receive awesome articles about learning Python and Computer Science in a fun and accessible way, straight to your inbox.

 Take your Python skills to the next level!

with our free email course on object oriented programming with Python