Federico Pintaluba
I'm a 27 years old developer, I have been coding for more than a decade, but I have focused in Android Development for the past 5 years. Here you will find all my projects, ideas, thoughts. Basically everything I made with <3.

HackerRank: Sock Merchant

Problem

John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

For example, there are n = 7 socks with colors ar = [1, 2, 1, 2, 1, 3, 2]. There is one pair of color 1 and one of color 2. There are three odd socks left, one of each color. The number of pairs is 2.

Function Description

Complete the sockMerchant function in the editor below. It must return an integer representing the number of matching pairs of socks that are available.

sockMerchant has the following parameter(s):

  • n: the number of socks in the pile
  • ar: the colors of each sock

Input Format

The first line contains an integer n, the number of socks represented in ar.
The second line contains n space-separated integers describing the colors ar[i] of the socks in the pile.

Constraints

Output Format

Return the total number of matching pairs of socks that John can sell.

Sample Input

9
10 20 20 10 10 30 50 10 20

Sample Output

3

Explanation

sock.png

John can match three pairs of socks.

Solution

So, at first glance, we know n is equal to ar size, but let’s dive deeper to find if this is exactly true in all edge cases.

We have the ar list provided with all the socks colors, let’s start by creating a Map with duplicates, let’s take a look at the groupBy inline function for Arrays.

inline fun <T, K> Array<out T>.groupBy(
    keySelector: (T) -> K
): Map<K, List<T>>

If we group the array by the current index (it), we will create a Map that for each socks color will have a List of repeated values. Let’s do a quick test to see how this works:

1 2 3 1 2 5
{1=[1, 1], 2=[2, 2], 3=[3], 5=[5]}

As you see, we have grouped duplicated values, and those numbers that are unique, are as well the only member of their key list.

In this quick test we did, we have 2 pairs (color 1 and 2), and 2 other colors without their pair.

Now, we need to identify how many pairs we have, we can do this pretty easily in Kotlin by mapping the List of values we have, into the size of the list by 2, let’s explain this further.

For each pair, we have a list of size 2, 2 divided by 2 will be 1 -> we have one pair.

For each sock color that doesn’t have it’s pair, the list size is 1, and 1 divided by 2 is 0.5, but as we are operating over Integers, the fractional part is discarded, which gives us 0. So, let’s map those values and see what we have.

ar.groupBy { it }.values.map { it.size / 2 }

As you see, we grab only the values from the Map we did by grouping our pairs, and then map them to a list of actual existing pairs, at the end, we should have a List of 1s and 0s.

Now, we have how many pairs of socks colors we have right? Are those 1s in our list, let’s sum them up!

Our final function looks like this:

fun sockMerchant(n: Int, ar: Array<Int>): Int {
    return ar.groupBy { it }.values.map { it.size / 2 }.sum()
}

Let’s try the sample input from the Problem, and see if we got exactly the sample output.

9
10 20 20 10 10 30 50 10 20

Running…

3

We did it, that’s exactly how many socks color pairs we have. Let’s submit the code in HackerRank and see if we pass all test cases.

Hope this helped you understand a fair solution made in Kotlin for this problem, if you have any suggestion or a better way of doing this in the same language, don’t hesistate on commenting below!

Share

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *