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

	Initialize a Dictionary
	For integer in the array:
	If the integer does not exist as a key in the dictionary
	Create a new key for that integer
	Set the value (frequency) to 1
	If the integer does exist as a key in the dictionary
	Increase it’s value by 1
	For each key in the Dictionary
	Divide by two
	Floor the result
	Add value to the pairs count
	return pairs

view raw gistfile1.txt hosted with ❤ by GitHub

In Python 3:

	def sockMerchant(n, ar):
	Colors = {}
	pairs = 0;
	i = 0;
	for i in range(len(ar)):
	if Colors.get(ar[i]) == None:
	Colors[ar[i]] = 1
	else:
	Colors[ar[i]] += 1
	for key, value in Colors.items():
	pairs += math.floor(value/2)
	return pairs

view raw gistfile1.txt hosted with ❤ by GitHub