2020 January 21
Nick Page on Unsplash

HackerRank Challenge: Sales By Match

Nick Page on Unsplash

Going over these challenges, I wanted to explain what steps I took to solve them. Even if they are not difficult, there is a temptation to assume one "already knows" and there might be gaps in their logic. I think it's good to process what it is that makes something work. Please do NOT copy/paste if you don't know how to solve it. It's really good for you if you think things through yourself!

There is a large pile of socks that must be paired by color. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

I already had a visual in my mind. There is a a bunch of disorganized socks - very much like my own sock drawer. There are a few "orange" socks, some "reds", maybe some "blues" (aka 1's, 4's, 13's), etc. What matters is we keep grabbing two socks of the same "color", fold them, and put them away.

sockMerchant has the following parameter(s):

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

Example: 9, [10, 20, 20, 10, 10, 30, 50, 10, 20]

Thoughts

So the outcome we want is knowing how many pairs we put together from this array. Personally, I find that n is not necessary because we can easily find that out by checking the length of the array given. ar.length

One obvious fact is that we know that we are starting with 0 pairs, but looking at this small example we can already reckognize there will be pairs to match with the possibility of some left over that do not have a pair to match with.

We could decide to go through the index linearly, but there is a chance we could be wasting our time (10, then 20, oh another 10?). However, another approach we can take is starting with one number 10 counting all of the instances of that number and taking the even number from rounding down.

The second method might be better because once we have elimiated all of the same number, there is a greater chance we have significantly decreased our "pile". We can keep repeating this pattern until there are no more possible pairs. That's when we can confidently state how many pairs there are.

Making use of Array.prototype.filter() can quickly find out how many of the same there are in a given array. Math.floor() helps with elimintating the left over sock. We can divide the result by 2.

Once we have figured out how many pairs of a certain number, we can use Array.prototype.filter() again to elimintate them from the pile until we reach the end.

Steps

  • Begin with a total of zero pairs

  • Create a "match" function to do the following:

    • Count how many of the same "sock" using Array.prototype.filter()
    • Divide by two to find how many pairs possible
    • Round down using Mathfloor()
  • Looping through the array:

    • Call the match function to add the number of pairs to our total (lather) match(number)
    • Then remove the already matched socks from the array (rinse) ar = ar.filter(e => e !== number)
    • Keep doing this until we reach the end (repeat)
  • Output the total number of pairs possible

Solution

Put it all together, the solution could look something like this!

Resources

Copyright © 2021. Jake Wantulok