C++ Program to get minimum difference between jigsaw puzzle pieces

In this article, we will discuss how to get minimum differences between jigsaw puzzle pieces in ++ with several ways.

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:

Output:

Explanation:

The variables and functions present in the program are:

• The "minDifference" 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 the necessary inputs from the user. After that, the "minDifference" function is called. In that function, the given array is sorted. A for loop is used to iterate through the elements of the array. After that, the difference between the values at the indices at "i" and "i+n-1". The minimum among all the differences is the result of the problem. That minimum difference is returned to the main function.

Approach 2:

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.