To obtain the ideal solution the sum of all possible combinations of K

weights adjacent to one another must give the same value of sum. In order

to achieve such a condition, the elements of all possible K combinations

must remain the same.

Eg : Consider the following set of weights where K = 2

W = [ 1 , 2 , 1 , 4 , 3 , 2 ]

The possible sums with K = 2 are 1 + 2 = 3 , 2 + 1 = 3 , 1 + 4 = 5 , 4 + 3 = 7 and 3 + 2 = 5 .

All other combinations will have weights that are not close to one another.

In order for all the possible combinations to give the same value of sum all the sets of

K = 2 taken in order must have the same weights.

Therefore this ideal set would have the form

W = [ 1 , 2 , 1 , 2 , 1 , 2] ; K = 2 and SUM = 3 FOR ALL COMBINATIONS

Ie the number of minimum possible exchanges would be 2. All other possibilities of

making an ideal set of weights would have an even greater number of exchanges required.

So to find the number of exchanges required we can simply consider K sets ( W1

,W 2 , … , WK) in which each set would have the weights that are present in the

same repeated position according to the order given to Tarun when summing up

In the above example the two sets would be :

W1 = [1 , 1 , 3] and W2 = [2 , 4 , 2]

After obtaining these sets we can convert all the values present in each of these sets to

the value that has the highest frequency in each set

Ie in W1 we can see that

Frequency of 1 = 2 and

Frequency of 3 = 1.

Therefore exchanging 3 with a weight of 1 from the infinite set of available weights will

allow us to accomplish the same.

And by converting the weight 4 in set W2 to 2 we can do the same there as well.

So in a total of 2 exchanges we can reach the required ideal set that has the sum as a

single value.

Therefore by considering the frequency of weights in each of the K sets and by

taking the sum of required exchanges in each set . We can find out the required

number of exchanges needed to reach the solution.