Sock merchant problem - Hackerrank
Post
Cancel

# Sock merchant problem - Hackerrank

Problem definition is available here

This is a classification problem where the element can repeat multiple times in the given array.

Like any other problem, this can be solved in multiple ways in kotlin.

### 1. Elegant - yet non performant solution

```1 2 3 4 5 fun sockMerchant(n: Int, ar: Array<Int>): Int { return ar.groupBy { it } .map { it.value.size/2 } // it is Map<Int, List<Int>> .sum() } ```

This is a straightforward solution

1. Read each value and create a map `Map<Int, List<Int>>`
2. Convert each key-value-entry into integer by computing the size of value array
3. Sum all elements in the integer list obtained from previous step

Though this looks elegant and kotlinish, we shouldn’t ignore the fact that it creates a Map with value list of identical elements. While what needed is just a counter mapped against each element.

### 2. Old school - manual computation

For this classification problem, `Map` is the ideal datastructure for grouping.

```1 2 3 4 5 6 7 8 9 10 fun sockMerchant(n: Int, ar: Array<Int>): Int { val map = mutableMapOf<Int, Int>() for (s in ar) { map[s] = (map[s] ?: 0) + 1 } return map.values.fold(0) { acc, v -> acc + v/2 } } ```

Here, we create a map `Map<Int, Int>` & increase the counter for each bucket. Then fold it. So, there is no value `List<Int>` created. Moreover, based on the unique values, the Map size constrained. At the end, the map values iterated through and folded into count.

Wait.. There is still room for improvement

We need a consolidated count, not the per element pair count. That means, the fold function can be avoided by adding another line to the first loop.

```1 2 3 4 5 6 7 8 9 10 11 val map = mutableMapOf<Int, Int>() var pairCount = 0 for (s in ar) { var count = (map[s] ?: 0) + 1 map[s] = count if (count % 2 == 0) { // For every second encounter, increase pairCount by one pairCount++ } } return pairCount ```

Be kind to GC, few more lines of code won’t hurt