How To Solve The Sock Merchant Challenge
How To Solve HackerRank’s Sock Merchant Code Challenge With JavaScript
Problem
The Sock Merchant challenge is basically the concentration card game but discarding the extras and just counting the pairs:
- AR is a single string of spaced numbers with values ranging between 1 and 100 — ex 10 11 20 31
- N is the number of values in AR between 1 and 100 (which could be useless if we’re just calculating the array length)
Goal
Write a function or functions that returns the total number of pairs found in the in the string (AR)
Covering Our Bases
Covering our bases, we need to make sure that:
- Number of item (values) of AR is in between 1 and 100
- N is an integer, between 1 and 100
- N = the total number of values of AR
Counting The Values Of AR
In order to get a better sense of how many values are in AR we need to convert the string to an array and count it.
function sockMerchant(n, ar) {
// setting the constraints
const min = 1;
const max = 100;
// if it's a string convert it to an array
// ex "10 31 11" = ["10", "31", "11"]
ar = (typeof ar === "string") ? ar.split(' ') : ar; // check if ar meets the requirements
if (ar.length >= min && ar.length <= max) {
// continue
}
}
Validating N
Next we need to make sure that N is an integer and matches the same number of values of AR.
function sockMerchant(n, ar) {
// setting the constraints
const min = 1;
const max = 100;
// if it's a string convert it to an array
// ex "10 31 11" = ["10", "31", "11"]
ar = (typeof ar === "string") ? ar.split(' ') : ar; // check if ar meets the requirements
if (ar.length >= min
&& ar.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === ar.length) {
// continue
}
}
Understanding The Problem
At first look at this, it looks like an array that I’m going to continue searching through for matches, which would lead me to believe that we’ll need to write a recursive function to continually go through. The concept would be to take the first value of the array, remove it from the equation for searching, and search the rest of the array for the next sequential pairing of that number.
Finding A Match
// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]// set the default number of pairs to count
let pairs = 0;// get first value
let find = ar[0]; // "1"// create new array but remove the first value
let newArr = ar.slice(1); // ["2", "1", "2", "1", "3", "2"]// find if there match sequentiall
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++;
}
Removing The Pair
Now that we found a match, let’s remove that match from the array, to make it ready to be searched again.
// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]// set the default number of pairs to count
let pairs = 0;// get first value
let find = ar[0]; // "1"// create new array but remove the first value
let newArr = ar.slice(1); // ["2", "1", "2", "1", "3", "2"]// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++;
}// removing the match, but creating a new array
newArr = [ ...newArr.slice(0, newArr.indexOf(find)), ...newArr.slice(newArr.indexOf(find) + 1)];
// ["2", "2", "1", "3", "2"]
Repeating The Process
Now that we have the new array, we’re ready to search through it again.
// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]// set the default number of pairs to count
let pairs = 0;// get first value
let find = ar[0]; // "1"// create new array but remove the first value
let newArr = ar.slice(1); // ["2", "1", "2", "1", "3", "2"]// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 1
}// removing the match, but creating a new array
newArr = [ ...newArr.slice(0, newArr.indexOf(find)), ...newArr.slice(newArr.indexOf(find) + 1)];
// ["2", "2", "1", "3", "2"]// get first value
find = newArr[0]; // "2"// create new array but remove the first value
newArr = newArr.slice(1); // ["2", "1", "3", "2"];// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 2
}
Already we see that there is pattern here of performing the same process, with that we can already assume that this will now be in a function.
Refactoring For Recursion
Not only should we refactor this as a function, but because we are making the array smaller and smaller, we can refactor this as a recursive function.
Before
// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]// set the default number of pairs to count
let pairs = 0;// get first value
let find = ar[0]; // "1"// create new array but remove the first value
let newArr = ar.slice(1); // ["2", "1", "2", "1", "3", "2"]// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 1
}// removing the match, but creating a new array
newArr = [ ...newArr.slice(0, newArr.indexOf(find)), ...newArr.slice(newArr.indexOf(find) + 1)];
// ["2", "2", "1", "3", "2"]// get first value
find = newArr[0]; // "2"// create new array but remove the first value
newArr = newArr.slice(1); // ["2", "1", "3", "2"];// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 2
}
After
// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]// the 3 values that keep repeating are
// the array, the value to search, and the counted pairs
function findPairs(ar, find, pairs) {
// if there is still parts of the array left to search through
if (ar.length > 0) {
// assuming that the first ar would be ar.slice(1)
// we can assume that
let newArr = ar;
// we don't need to define find because we can assume
// that the first find is being send to us find = ar[0]
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 1
}
// 1. next we need to create new array
// but remove the first value
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments
return findPairs(
[ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)],
// ["2", "2", "1", "3", "2"]
newArr[0], // "2"
pairs
);
}
// ultimate value we are returning
return pairs;
}
Looks good, right? Not quite. What about when we don’t find a pair, how would I function work?
Finding The Bug
// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]findPairs(AR.slice(1), AR[0], 0);// ar = ["2", "1", "2", "1", "3", 2"]
// find = "1"
// pairs = 1// [ ...ar.slice(0.. = ["2", "2", "1", "3", "2"]
// find = ar[0] = "2"
// pairs = 2// [ ...ar.slice(0.. = ["2", "1", "3", "2"] (Something went wrong)
// find = ar[0] = "2" (Don't think should be right)
// pairs = 3 (Wait, what?)// [ ...ar.slice(0.. = ["1", "3", "2"]
// find = ar[0] = "2"
// pairs = 4 (Very wrong)// [ ...ar.slice(0.. = ["1", "3"]
// find = ar[0] = "1"
// pairs = 5 (That doesn't make sense)// [ ...ar.slice(0.. = ["3"]
// find = ar[0] = "1"
// pairs = 5 (Still wrong)// [ ...ar.slice(0.. = ["3"] (This should be gone)
// find = ar[0] = "3" (This is wrong)
// pairs = 6 (Still wrong)// Results = 6 pairs vs expected 2 (very wrong)
So where did we go wrong? Let’s look at the last instance just before things go wrong and walkthrough it.
// [ ...ar.slice(0.. = ["2", "2", "1", "3", "2"]
// find = ar[0] = "2" (This is where things go wrong)
// pairs = 2Two (2) should be removed from the AR slice, not just the item we just found (1). We need to refactor this as:
Before
...
// 1. next we need to create new array
// but remove the first value
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments
return findPairs(
[ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)],
newArr[0], // "2"
pairs
);
...After
...
// 1. next we need to create new array
// but remove the first value
// 1b. remove all the new first index "2"
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments
newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)]
return findPairs(
newArr.slice(1),
newArr[0], // "2"
pairs
);
...Run it again:
// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]findPairs(AR.slice(1), AR[0], 0);// ar = ["2", "1", "2", "1", "3", "2"]
// find = "1"
// pairs = 1// ar.slice(1) = ["2", "1", "3", "2"]
// find = "2"
// pairs = 2// ar.slice(1) = ["3", "2"]
// find = "1"
// pairs = 2// ar.slice(1) = ["3", "2"] (Somethings not right)
// find = "3" (Going wrong)
// pairs = 3 (Very wrong)
We’ve gotten closer, but we’re missing one last thing.
Handling No Pair Found
The part where it went wrong is when there was no pair found and we needed to pass through the array again. Based on our redeclaration of newArr, it’s based on finding a value that isn’t found:
// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]...
// ar.slice(1) = ["3", "2"]
// find = "1"
// pairs = 2
...newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];// gives us
// ["3", "3", "2"]
// expected
// ["2"]
If we have the array, what we should be really sending is:
newArr = newArr.slice(1);// gives us
// ["2"]
So we need to account for this only in the case that the find is not found in newArr.
Before
...
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++;
}
newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];
...After
...
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 1. next we need to create new array
// but remove the first value
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments
newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];
} else {
newArr = newArr.slice(1);
}
...
But wait, are we doing newArr.slice(1) already in the return?
After again:
...
// find if there match sequential
if (newArr.indexOf(find) > -1) { // index 1
// a match was found, increment pairs
pairs++; // 1. next we need to create new array
// but remove the first value
// 2. send the new find = newArr[0]
// 3. continue passing pairs to make sure it increments
newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];
}
return findPairs(
newArr.slice(1),
newArr[0],
pairs
);
...
Run it again:
// Example 1 - Assuming
// N = 7
// AR = ("1 2 1 2 1 3 2").split(' ');
// ["1", "2", "1", "2", "1", "3", "2"]findPairs(AR.slice(1), AR[0], 0);// ar = ["2", "1", "2", "1", "3", "2"]
// find = "1"
// pairs = 1// ar.slice(1) = ["2", "1", "3", "2"]
// find = "2"
// pairs = 2// ar.slice(1) = ["3", "2"]
// find = "1"
// pairs = 2// ar.slice(1) = ["2"]
// find = "3"
// pairs = 2// Returns = 2 (Correct solution)
Solution
Now that we figured it out, let’s put everything together:
function findPairs(ar, find, pairs) {
if (ar.length > 0) {
let newArr = ar;
if (newArr.indexOf(find) > -1) {
pairs++;
newArr = [ ...newArr.slice(0, newArr.indexOf(find)),
...newArr.slice(newArr.indexOf(find) + 1)];
} return findPairs(
newArr.slice(1),
newArr[0],
pairs
);
}
return pairs;
}function sockMerchant(n, ar) {
const min = 1;
const max = 100;
ar = (typeof ar === "string") ? ar.split(' ') : ar;
if (arar.length >= min
&& ar.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === ar.length) {
return findPairs(ar.slice(1), ar[0], 0);
}
// if does not meet criteria return 0
return 0;
}
Test Cases
// N = 9, AR = "10 20 20 10 10 30 50 10 20", Expected 3
// N = 15, AR = "6 5 2 3 5 2 2 1 1 5 1 3 3 3 5", Expected 6
// N = 1, AR = "100", Expected 0
// N = 1, AR = "101 100", Expected 0
// N = 0, AR = "", Expected 0
// N = 101, AR = "10000", Expected 0sockMerchant(9, "10 20 20 10 10 30 50 10 20"); // 3 ✅
sockMerchant(15, "6 5 2 3 5 2 2 1 1 5 1 3 3 3 5"); // 3 ✅
sockMerchant(1, "100"); // 0✅
sockMerchant(1, "101 100"); // 0✅
sockMerchant(0, ""); // 0 ✅
sockMerchant(101, "10000"); // 0✅
Our code passed the test case scenarios, meets the requirements, and ultimately passes the challenge.
Feedback?
If you have any tips or recommendations on how this can be solved better or optimized, I would love to talk in the comments and welcome any feedback.
If you got value from this, please give this article some applause 👏 and share it on twitter 🐦 or other social media platforms. Thanks again for reading. 🙏
Please also follow me on twitter: @codingwithmanny and instagram at @codingwithmanny.
