C++ Program To Get Minimum Difference Between Jigsaw Puzzle Pieces

In this guide, we will explore methods to minimize the variations between jigsaw puzzle pieces in C++ using various techniques.

Problem statement:

Alice has some friends, so he wants to buy jigsaw puzzles for his friends. Therefore, he went to a nearby shop. There are a number of puzzles present in the shop. Each has a different number of jigsaw puzzle pieces. After that, he wants to select a number of puzzles to give his friends. Here, Bob wants to minimize the difference between the number of pieces in the largest puzzle and the smallest puzzle. It means he wants to buy puzzles that have almost the same number of pieces in the puzzle.

• ✅ The number of pieces in the largest puzzle is x.
• ✅ The number of pieces in the smallest puzzle is y.
• ✅ After that, he wants to find out x-y.
• ✅ The total number of puzzles in the shop is (m).
• ✅ Total number of friends (n).
• ✅ The puzzles are in an Array (A).

Test case 1:

Total number of puzzles m: 6

Array A: [ 10, 12, 10, 7, 5, 22]

Number of friends n: 4

Output: 5

Explanation: the difference between 10 and 5 is 5

Test case 2:

Total number of puzzles m: 5

Array A: [ 3, 8, 12, 15, 20]

Number of friends n: 3

Output: 7

Explanation: The difference between 15 and 8 is 7

Approach 1:

#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>
using namespace std;
int minDifference(vector<int>& A, int n) {
    sort(A.begin(), A.end());
    int minDiff = INT_MAX;
    for (int i = 0; i <= A.size() - n; ++i) {
        int diff = A[i + n - 1] - A[i];
        minDiff = min(minDiff, diff);
    }
    return minDiff;
}
int main() {
    int m, n;
    cout << "Enter the number of puzzles (m): ";
    cin >> m;
    vector<int> A(m);
    cout << "Enter the number of friends (n): ";
    cin >> n;
    cout << "Enter the number of pieces for each puzzle:\n";
    for (int i = 0; i < m; ++i) {
        cin >> A[i];
    }
    int minDiff = method2(A, n);
    cout << "The least possible difference between the number of pieces in the largest and smallest puzzle: " << minDiff << endl;
    return 0;
}

Output:

Explanation:

The variables and functions found in the program include:

• ✅ The "minDifference" function is designed to accept a vector and the number of friends as arguments, with an integer return type. Within the main function, m denotes the total number of puzzles, n represents the number of friends, and the array "A" signifies the size of each puzzle in the shop.

The program commences by gathering all essential inputs from the user. Following this, the "minDifference" function is invoked. Within this function, the provided array undergoes sorting. Utilizing a for loop, the array elements are iterated through. Subsequently, the difference between the values at the indices "i" and "i+n-1" is computed. The minimum difference among all these calculations is identified as the solution to the problem. This minimum difference is then passed back to the main function.

Approach 2:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int method2(vector<int>& arr, int n){
    sort(arr.begin(), arr.end());
    int target= arr.size()-n;
    int count=0;
    int first=0;  // removing first element
    int last=arr.size()-1;  // removing last element
    while(count < target){
        int diff1= arr[last]-arr[first+1];
        int diff2= arr[last-1]-arr[first];
        if(diff1 > diff2){
            last--;
        }else{
            first++;
        }
        count++;
    }
    for(int i=first; i<=last; i++){
        cout << arr[i] <<" ";
    }
    cout << endl;
    return arr[last]-arr[first];
}
int main() {
    int m, n;
    cout << "Enter the number of puzzles (m): ";
    cin >> m;
    vector<int> A(m);
    cout << "Enter the number of friends (n): ";
    cin >> n;
    cout << "Enter the number of pieces for each puzzle:\n";
    for (int i = 0; i < m; ++i) {
        cin >> A[i];
    }
    int minDiff = method2(A, n);
    cout << "The least possible difference between the number of pieces in the largest and smallest puzzle: " << minDiff << endl;
    return 0;
}

Output:

Explanation:

The variables and functions present in the program are:

• ✅ The "method2" function takes the input vector and number of friends as parameters. The return type of the function is integer. In the main function, m represents the total number of puzzles, n represents the number of friends and array "A" represents the size of each puzzle in the shop.
• ✅ The program starts by taking all necessary inputs from the user. The vector and number of friends are passed to the method2 function. In this function. The array is sorted in ascending order. After that, we will find how many puzzles should be removed and store that value in the target variable. Now, we initialize two variables, "first' and "last", with 0 and length of array-1.
• ✅ Another variable count is declared and initialized with 0. After that, a while loop is used. This loop will terminate if the count is greater than the target. Now, in the while loop, two more variables are used. The "diff1" is the difference if the first element is removed, and "diff2" is the difference if the last element is removed. After that, we check if the "diff1" is greater than the "diff2". We will decrement the "last" variable; otherwise, we will increment the "first" variable.
• ✅ At last, the minimum difference will be the difference between the values at the indices of "last" and "first". It is returned to the main function. In the main function, the result is printed to the console.