Chopsticks Pairing Problem Using C++

Filed Under: C++
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

close
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors