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
n = 7
ar = [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.
Constraints
- 1 <= n <= 100
- 1 <= ar[i] <= 100 where 0<=i<=n
Sample Input
9
10 20 20 10 10 30 50 10 20
Sample Output
3
Solution
You are given the following to start with:
#include <bits/stdc++.h>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);
/*
* Complete the 'sockMerchant' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER_ARRAY ar
*/
int sockMerchant(int n, vector<int> ar) {
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string n_temp;
getline(cin, n_temp);
int n = stoi(ltrim(rtrim(n_temp)));
string ar_temp_temp;
getline(cin, ar_temp_temp);
vector<string> ar_temp = split(rtrim(ar_temp_temp));
vector<int> ar(n);
for (int i = 0; i < n; i++) {
int ar_item = stoi(ar_temp[i]);
ar[i] = ar_item;
}
int result = sockMerchant(n, ar);
fout << result << "\n";
fout.close();
return 0;
}
string ltrim(const string &str) {
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);
return s;
}
string rtrim(const string &str) {
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);
return s;
}
vector<string> split(const string &str) {
vector<string> tokens;
string::size_type start = 0;
string::size_type end = 0;
while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));
start = end + 1;
}
tokens.push_back(str.substr(start));
return tokens;
}
We want to focus on the sockMerchant() function. We will need to keep track of the number of pairs in ar and we also know we will need to return that number as an integer.
int sockMerchant(int n, vector<int> ar) {
int numberOfPairs = 0;
return numberOfPairs;
}Next, we should sort the array, ar. We can do this by utilizing the sort() function which takes in the the beginning and end of an array. These can be found by using the .begin() and .end() functions. Sorting the array will allow us to know that each number will be grouped together in the array. Since the numbers represent a different color, we can use these groupings to determine pairs.
int sockMerchant(int n, vector<int> ar) {
int numberOfPairs = 0;
sort (ar.begin(), ar.end());
return numberOfPairs;
}Now that the array is sorted, we need to traverse it to find the pairs. We can use a for loop for this. Let’s think about our logic. If ar[0] and ar[1] are both 20 then we have a pair so we can add one to our number of pairs.
for(int i = 0; i< n-1; i++){
if(ar[i] == ar[i+1]){
numberOfPairs = numberOfPairs + 1;
}
} This looks pretty good, but what happens if ar[0], ar[1], and ar[2] are all 20? We would end up counting 2 pairs when we only have 1. We will need to skip ahead in our index so that we don’t compare ar[1] again.
for(int i = 0; i< n-1; i++){
if(ar[i] == ar[i+1]){
numberOfPairs = numberOfPairs + 1;
i = i+1;
}
} Let’s walk through an example.
n = 4
ar = [20, 20, 20, 30]
| i | i+1 | If statement | numberOfPairs |
| 0 | 1 | True | 1 |
| 2 | 3 | False | 1 |
We start at i = 0. Since ar[0] equals ar[1], both are 20, the if statement is true. This means that within the if statement i is set to 1. When we return to the for loop i then becomes 2. Since ar[2] = 20 and ar[3] = 30 the if statement returns false. The index must stay less than n-1. In this case, n=4 so i < 3.
The finished solution:
#include <bits/stdc++.h>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);
/*
* Complete the 'sockMerchant' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER_ARRAY ar
*/
int sockMerchant(int n, vector<int> ar) {
int numberOfPairs = 0;
sort (ar.begin(), ar.end());
for(int i = 0; i< n-1; i++){
if(ar[i] == ar[i+1]){
numberOfPairs = numberOfPairs + 1;
i = i+1;
}
}
return numberOfPairs;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string n_temp;
getline(cin, n_temp);
int n = stoi(ltrim(rtrim(n_temp)));
string ar_temp_temp;
getline(cin, ar_temp_temp);
vector<string> ar_temp = split(rtrim(ar_temp_temp));
vector<int> ar(n);
for (int i = 0; i < n; i++) {
int ar_item = stoi(ar_temp[i]);
ar[i] = ar_item;
}
int result = sockMerchant(n, ar);
fout << result << "\n";
fout.close();
return 0;
}
string ltrim(const string &str) {
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);
return s;
}
string rtrim(const string &str) {
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);
return s;
}
vector<string> split(const string &str) {
vector<string> tokens;
string::size_type start = 0;
string::size_type end = 0;
while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));
start = end + 1;
}
tokens.push_back(str.substr(start));
return tokens;
}
