Sales by Match Problem Description
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
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 sock Merchant 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.
Constraints
Sample Input
n = 9
ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]
Explanation
Sample Output
3
Solution
I used JavaScript to solve this problem.
Step #1
To write the solution, we need to declared a function called 'sockMerchant' which will accept two parameters:
n = the number of socks in the pile
ar = the colors of each sock
function sockMerchant(n, ar) {
//We will write the code here
};
Step #2
Outside this function, we will declare another function called 'isEven' which will be invoked later on to validate if a number is Even or Odd.
Even numbers are exactly divisible by 2. Meaning when divided by 2 the remainder is zero. Otherwise, the number is odd. We use the modulus operator (%) to get the remainder of a division.
To identify Even numbers, we need to return 'true' every time we get a 0 when using the mod operator.
However, 0 is a falsy value, meaning JavaScript will return false if a 0 is returned. This is changed using the logical not operator '!'.
function isEven(num) { return !(num % 2)};
Step #3
Now I will start describing the code written inside the 'sockMerchant' function.
First, an empty object called 'counts' it's declared. The object keys will be equal to the unique values of the array 'ar'.
The value of every key will show how many times that key is repeated in the array 'ar'.
function sockMerchant(n, ar) {
//We will write the code here
const counts = {};
};
Step #4
To start populating the 'counts' object we will use the method 'forEach', through which we iterate through every index of the array 'ar'.
Example:
Let's suppose the first value for 'x' is '1', the first object key will be declared by the expression 'counts[1]'.
The program will try to set the value for this key with the expression
'(counts[1] || 0) + 1'
This sentence can be read as follows:
"If the key 'counts[1]' can be converted to True (if the key already exists), return its value, else return '0' ".
function sockMerchant(n, ar) {
const counts = {};
ar.forEach((x) => {
counts[x] = (counts[x] || 0) + 1;
});
};
Step #5
Then, the variable 'pairs' is declared to store the total number of socket pairs.
function sockMerchant(n, ar) {
const counts = {};
ar.forEach((x) => {
counts[x] = (counts[x] || 0) + 1;
});
let pairs = 0;
};
Step #6
To get the total number of socket pairs, we need to iterate through the object 'counts'. It will be used the variable 'item' to iterate for every key of the object 'counts'. Every 'item' represents a color of sockets, and when accessing to its value with the expression 'counts[item]' we will get the total number of sockets available for that color.
Then we check if the total number of sockets available for a specific color is Even. If true, we divide this number by 2 to get the number of socket pairs for that color and sum the result to the variable "pairs".
If the total number of sockets available for a specific color is Odd. We subtract 1 unit, divide by two and we sum the result to the "pairs" variable.
function sockMerchant(n, ar) {
const counts = {};
ar.forEach((x) => {
counts[x] = (counts[x] || 0) + 1;
});
let pairs = 0;
for (const item in counts){
if(isEven(counts[item])) {
pairs += counts[item]/2;
}else{
pairs += (counts[item]-1)/2;
}
}
}
Step #7
At the end, we return the variable 'pairs' which will represent the total number of socket pairs existing in the array 'ar'.
function sockMerchant(n, ar) {
const counts = {};
ar.forEach((x) => {
counts[x] = (counts[x] || 0) + 1;
});
let pairs = 0;
for (const item in counts){
if(isEven(counts[item])) {
pairs += counts[item]/2;
}else{
pairs += (counts[item]-1)/2;
}
}
return(pairs);
}