7

Chopsticks Pairing Problem Using C++

 2 years ago
source link: https://www.journaldev.com/62140/chopsticks-pairing-problem-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Chopsticks Pairing Problem Using C

Today, we’ll learn to solve the chopsticks pairing problem using C++. It is a very popular problem from CodeChef. The chopsticks pairing problem is greedy. This has already been asked about during many coding competitions. We’ll learn to solve this problem most efficiently. So without wasting any time, let’s quickly get started.

Also read: Load Balancing Problem Using C++

Problem Statement

There are N chopsticks of different lengths. You need a pair of chopsticks to eat. Two chopsticks can only be paired if the difference in their lengths is less than or equal to D. You have to find out the maximum number of pairs you can form from the chopsticks.

For example,

N: 5
Chopsticks: [5 3 6 8 1]
D: 2
Solution: 2 pairs
Explaination:
We can pair [3, 5], and [6, 8]
N: 5
Chopsticks: [4 3 9 3 1]
D: 2
Solution: 2 pairs
Explaination:
We can pair [1, 3], and [3, 4]

Approach

Key To Solving This Problem

Sort the chopsticks in ascending order of height. Then, pair each chopstick to its next chopsticks if the difference in their heights is less at most D.

  • This choice is a greedy choice because we sorted the chopsticks based on their heights.
  • Now, let’s see why does it work?
    • Let’s suppose that the chopsticks are in sorted order.
    • Start from the first chopstick on the list.
    • If the pair [i, i + 1] is not possible. Then i can not be paired with any other chopstick.
      • Because with the increasing position, the length of the chopsticks does not decrease.

So, our greedy choice will be to sort the chopsticks in ascending order of height.

Pseudocode

Below is the step-by-step process that we’ll follow to implement the algorithm.

  • Greedy Choice: Pair the chopsticks with the next chopstick in the sorted vector.
  • Sort the chopsticks in increasing order of height.
    • sort(chopsticks.begin(), chopsticks.end());
  • Initialize a variable to store the answer.
    • int max_pairs = 0;
  • Start iterating over the sorted vector.
    • for(int i = 0; i < N; i++)
    • During each iteration, fulfil the greedy choice, and increase the count.
      • max_pairs++;
  • Finally, return the answer.
    • return max_pairs;

Chopsticks Pairing Problem Using C++ Program

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int max_chopsticks_pairs(vector <int> chopsticks, int N, int D)
{
// first sort the chopsticks in increasing order of length
// by default the STL sort function sorts in ascending order
sort(chopsticks.begin(), chopsticks.end());
// variable to store the answer
int max_pairs = 0;
// now start to iterate over the sorted vector
// and pair the chopsticks
for(int i = 0; i < N - 1; i++)
{
// pair only if the difference in the lengths is
// at most D
if((chopsticks[i + 1] - chopsticks[i]) <= D)
{
// increase the count
max_pairs++;
// increase the value of i
i++;
}
}
// return the answer
return max_pairs;
}
int main()
{
// take the input
cout << "Enter the number of chopsticks" << endl;
int N;
cin >> N;
// vector to store the lengths of the chopsticks
vector <int> chopsticks(N);
cout << "Enter the lengths of the chopsticks" << endl;
for(int i = 0; i < N; i++)
{
int len;
cin >> len;
chopsticks[i] = len;
}
// take input the value of D
cout << "Enter the value of D" << endl;
int D;
cin >> D;
// display the results
cout << "The maximum number of pairs that can be formed are: " << max_chopsticks_pairs(chopsticks, N, D) << endl;
return 0;
}
Chopsticks Pairing Problem Code
Chopsticks Pairing Problem Code

Output

Chopsticks Pairing Problem Output
Chopsticks Pairing Problem Output

Conclusion

In this article, we learned to solve the chopsticks pairing problem using C++. We used the STL(Standard Template Library) sort function to make use of our greedy choice. In the end, we implemented a C++ program to demonstrate the working of our solution. That’s all for today, thanks for reading.

Further Readings

To learn more about C++ programming, data structures and algorithms, you can go through the following articles.

https://www.journaldev.com/61277/first-non-repeating-character-running-stream-c

https://www.journaldev.com/61251/generic-programming-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK