HackerRank – Sock Merchant solution

by

In this article, I’ll explain how to solve the Sock Merchant algorithm problem on HackerRank.

Problem statement: You’re given an integer array and need to count the number of pairs of matching integers. The integers will be between 1 and 100.

For example, [3,1,3] has one matching pair (the 3s match).

Approach

First, we know an integer can be paired if it appears in the array twice. For example:

Input = [3,1,3]
Pairs = (3,3)
Count = 1Code language: plaintext (plaintext)

Integer 3 appears twice, so it could be paired once. Integer 1 appears once, so it couldn’t be paired.

We can generalize this and say an integer that appears N times results in N / 2 pairs. For example:

Input = [3,1,3,3,3,1,2]

3 appears 4 times, resulting in 4 / 2 = 2 pairs.
1 appears 2 times, resulting in 2 / 2 = 1 pair.
2 appears 1 time, resulting in 1 / 2 = 0 pairs.

Count = 3 pairs.Code language: plaintext (plaintext)

Note: If an integer appears an odd number of times, integer division takes care of that (dividing two integers in code results in an integer, which chops off decimals. This is why 1 / 2 = 0 in the example above).

This means we don’t need to actually find the pairs. Instead, we’ve reduced the problem to counting the frequency of each integer and dividing the counts by 2. At the end, we can get sum the pair counts to get the total. This can be expressed in the following pseudocode:

get counts of each integer
divide each count by 2 to get the number of pairs
sum the pair count
Code language: plaintext (plaintext)

I’ll show how to implement this code next.

Code

Here’s an example of implementing the algorithm to solve the problem (this is using C#):

public static int sockMerchant(int n, List<int> ar)
{
	int[] intCounts = new int[101];
	
	foreach(int i in ar)
	{
		intCounts[i]++;
	}
	
	int pairs = 0;
	foreach(int count in intCounts)
	{
		pairs += count / 2;
	}

	return pairs;
}
Code language: C# (cs)

Usually with frequency counting problems, you’d loop through the values and add counts to a dictionary. But in this problem, we know the range of integers will be between 1 and 100 (according to the problem statement). This means we can use an array instead of a dictionary, which avoids overhead costs. Note: Array size 101 = max value in range (100) + 1, because arrays are 0-based.

This algorithm can be coded in a few different ways, including calculating the pairs while you’re counting. That’s a bit of a micro-optimization though, especially since we know the input size is so small (up to 100 integers). Code readability is more important than a micro-optimization.

Related Articles