April 21, 2018 May 17, 2018 8 min reading

Warm-up Challenges Sock Merchant

I'm posting about my solutions to the HackerRank challenges as a way to improve my learning, reinforce my knowledge, and establish an understanding of the concepts covered. If I help someone by sharing along the way, even better!

Sock Merchant is one of the initial challenges with 'EASY' difficulty.

What's the challenge?

John works at a clothing store. He has a big pile of socks that he must sort by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with the corresponding colors exist.

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

What do we have to do?

A function that should return an integer representing the number of matching pairs of socks available.

Parameters

• n = the number of socks in the pile

• ar = the colors of each sock in an array

Sample Input

9
10 20 20 10 10 30 50 10 20

Sample Output

3

Solution

function sockMerchant(n, ar) {

	let socks = {},
		count = 0,
		i = 0;

	for (i = 0; i < n; i++) {
		if (ar[i] in socks) {
			socks[ar[i]] += 1;
		} else {
			socks[ar[i]] = 1;
		}
	}

	Object.keys(socks).map(el => {
		count += ~~(socks[el] / 2);
	})

	return count;
}

Logic

let socks = {},
	count = 0,
	i = 0;

First I created three variables; socks is an object that records the count of each type of sock; count to keep count of the number of pairs of socks; i to iterate the forloop;

for loop

I've created a for that will loop through the sock color array. It will iterate n times, which is the given amount of socks on the stack. for (var i = 0; i < n; i++)

The condition if checks if the color exists in our object socks: if (ar[i] in socks)
If it exists, increment the count for that color by one: socks[ar[i]] += 1;
If not, create a key with that color and set it to 1. socks[ar[i]] = 1;

After the socks have been counted, execute a map on the socks object, so an element will be separated for each key: Object.keys(socks).map(el => {

Then I calculate the number of pairs by dividing the number of "socks" of one color socks[el] / 2 and then apply the answer, two tildes (bitwise NOT).

I used the bitwise NOT as a substitute for the Math.floor(), as it performs the same operation much faster , as you can check in https://jsperf.com/jsfvsbitnot

Finally, I end the function by returning the final count.

Extra Solutions

Other languages that I speak

Ruby

def sockMerchant(n, ar)
	socks = Hash.new { | hash, key | Hash[key] = 0 }
	count = 0

	ar.each { | color | socks[color] += 1 }
	socks.each_value { | el | count += (el / 2) }

	count
end

PYTHON 2 & 3

def sockMerchant(n, ar):
	socks = collections.Counter(ar)
	count = 0

	for el in socks:
		count += socks[el] // 2
			
	return count

GOLANG

func sockMerchant(n int32, ar []int32) int32 {
	var count, i int32

	socks := make(map[int32]int32)
	for i = 0; i < n; i++ {
		socks[ar[i]]++
	}
	for _, el := range socks {
		count += (el / 2)
	}
	return count
}

SCALA

def sockMerchant(n: Int, ar: Array[Int]): Int = {
	val socks = ar.groupBy(c => c)
	val pairs = socks.map(el => el._2.length / 2)
	val count = pairs.sum
	return count;
}

JAVA 7 & 8

static int sockMerchant(int n, int[] ar) {
	HashSet<Integer> socks = new HashSet<Integer>();
	int count = 0;
					
	for (Integer i:ar) {
		if (socks.contains(i))
			socks.remove(i);
			count++;
		else
			socks.add(i);
	}
	return count;
}

PHP

function sockMerchant($n, $ar) {
	$socks = array_count_values($ar);
	$count = 0;

	foreach ($socks as $el) {
		$count += intdiv($el, 2);
	}
	return $count;
}

Thought: Having faith is to sign a blank sheet of paper and let God write what he wants.