# HackerRank: Sales By Match

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`

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:**

**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! :)*

# 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”: