Star Gazers
Published in

Star Gazers

HackerRank: Sales By Match

image of socks — Education.com

If you’re like me, practicing a code challenge is probably the one thing that’s got you feeling extremely nervous about that technical interview coming up soon, or even tomorrow! That’s okay, they are meant to be challenging, otherwise, they wouldn't be called code challenges!

Luckily, they are not impossible to solve, unless someone out there has created the world's most complicated algorithm — which would just be incredibly unnecessary.

Aside from all of the “what ifs”, I am here to talk about an algorithm I struggled solving!

Sales By Match

Problem:

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.

Example:

n = 7
r = [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.

sockMerchant has the following parameter(s):

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

Returns

int: the number of pairs

Input Format

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

Sample Input

STDIN Function
— — — — — — —

9 
10 20 20 10 10 30 50 10 20

Function

n = 9
ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]

Sample Output

3
HackerRank

From what I have gathered, we have out integer (n) that tells us how many “socks” are in our array. We have an array, in that array we have a few repeating elements that represent a sock. We also have an output of just an integer of how many pairs of socks we should be returning. So far, so good!

How should we approach this problem?

What I like to do is ask myself, “What can we do with what we know?”, this usually leads to verbal pseudocode

Ex:

//check to see if array === valid
//we need a counter for how many pairs we encounter
//i can create an object to store a key/value pair
// can now iterate over the array
--> //for every sock in array, if that sock has already been encountered we add 1 to it's value || if not we start off with 1
ex:
sock: num
1st encounter 20: 1
2nd encounter 20:2
//iterate over the array again to count the pairs
--> // for every sock in array, if that sock's value is divisible by 2 increment our counter !
20: 2 <-- 2 % 2 === 0 //=> yes!
counter += 1
//return our total pairs

The Code:

salesMerchant code snippet

Time Complexity

The time complexity of just one for of loop is O(n) which is called “Linear Time”. However, since I used two for of loops that is what is called “Quadratic Time” because I am going through each element in the array a second time! Therefore, my solution would have a time complexity of O(2n) and when we drop the constant, it would be O(n) , which is an ideal solution.

Considering the fact that I have an obj variable to store each element into a key/value pair. I believe this is called a “Hash Table”. Since my solution is looking up an object property is O(1), this will result in giving my solution a little boost in speed, making it now O(n)!

Thank you for reading! Keep Coding! Keep Learning, Keep Growing! :)

Night Programming — Metin Seven Pinterest

References:

What helps me understand Big O Notation:

If you want to try your hand at optimizing my code better here is the link to “Sales By Match”:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store