Move all equal objects to the median location of those objects.
So if you have
{5,5,1,5,1,1,1,5,1,5}Then we would move the fives to index 3 and the 1's to index 5. Why? Consider any candidate position to place a collection of objects. If there are x more objects to the left of that position than to the right, we could reduce the total moves by x simply by moving the position one to the left. We could continue reducing the moves until there are an equal number of objects to the left as to the right. That position is the median of that subset of objects. So to get the result they are asking for, you have to find the median location for each distinct value in the array and find the sum of the differences between each value and the median. I would consider using a map to store the locations indexed by value. Then iterate over the map and process each set of locations one by one. Don On Mar 23, 4:59 am, rakesh kumar <rkchoudhary0...@gmail.com> wrote: > > There are N objects kept in a row. The ith object is at position x_i. You > > want to partition them into K groups. You want to move all objects > > belonging to the same group to the same position. Objects in two different > > groups may be placed at the same position. What is the minimum total amount > > by which you need to move the objects to accomplish this? > > > Input: > > The first line contains the number of test cases T. T test cases follow. > > The first line contains N and K. The next line contains N space seperated > > integers, denoting the original positions x_i of the objects. > > > Output: > > Output T lines, containing the total minimum amount by which the objects > > should be moved. > > > Constraints: > > 1 <= T <= 1000 > > 1 <= K <= N <= 200 > > 0 <= x_i <= 1000 > > > Sample Input: > > 3 > > 3 3 > > 1 1 3 > > 3 2 > > 1 2 4 > > 4 2 > > 1 2 5 7 > > > Sample Output: > > 0 > > 1 > > 3 > > > Explanation: > > > For the first case, there is no need to move any object. > > For the second case, group objects 1 and 2 together by moving the first > > object to position 2. > > For the third case, group objects 1 and 2 together by moving the first > > object to position 2 and group objects 3 and 4 together by moving object 3 > > to position 7. Thus the answer is 1 + 2 = 3. > > > I thought of sorting the array and then calculating difference but no > > success.Please help -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
