Coding Problem: Sock Merchant program (Finding Pairs)

HackerRank

View the original problem at HackerRank

Problem Verbatim: Given a series of numbers, find the number of times unique pairs appear and return the total pairs as an integer.

The story behind this problem disguises a fairly straightforward task. John works at a clothing store and needs to sort a pile of socks by color, with an integer representing each color. Given an array of numbers, find the total amount of unique pairs in the array.

Example Input:

n = 7 (Size of the array)

color_array = [10, 20, 40, 10, 30, 20, 10]

Example Output:
pairs = 2

Background
First off, the fact that each number represents a color is excess information. Regardless of the array being:

color_array = [10, 20, 40, 10, 30, 20, 10]

or

color_array = [“blue”, “green”, “red”, “blue”, “white”, “green”, “blue”]

The program should run regardless because, essentially, this is a frequency program.

Let’s continue with our array, but let’s make it a little bigger:

color_array = [10, 20, 40, 10, 30, 20, 10, 20, 50, 10, 30, 10, 40, 50, 20]
n = 15

Looking at this array, we see that there are five 10’s, four 20’s, two 30’s, two 40’s, and two 50’s. A better way of writing this would be:

10: 5, 20: 4, 30: 2, 40: 2, 50: 2

Hopefully this format is beginning to look familiar. In this example, we are representing the frequency of our values in a dictionary, the key being the integer and the value being the frequency.

Remember, however, that we are looking for unique pairs. For this, simply divide each value by 2.

{ 10: 2.5, 20: 2, 30: 1, 40: 1, 50: 1 }

Almost there. We still need to account for odd frequencies, like the integer 10. Because we can’t have half a pair, we’ll need to round down. That’s simple with the floor function.

floor(2.5) = 2

Alright! Let’s put this all together.

Pseudocode



In Python 3: