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 thi…

MinMovesSolution.java

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
import java.io.*;
import java.util.*;

class MinMovesSolution
{
    public static void main(String [] args) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        String line = null;
        int noOfTestCases = sc.nextInt();
        int n=0;
        int k=0;
        for(int i =0;i<noOfTestCases;i++){
            n=sc.nextInt();
            k=sc.nextInt();
            int[] array =new int[n];
            for(int num=0;num<n;num++){
                array[num]=sc.nextInt();
            }
             Arrays.sort(array);
            System.out.println(minMoves(array,k));
        }
            
    }
     public static int minMoves(int[] arr, int k) {
        int n = arr.length;
        int min[][] = new int[n][k+1];
        for(int i=0; i<n; i++)
            min[i][0] = Integer.MAX_VALUE;
        for(int i=0; i<n; i++) {
            for(int j=1; j<=k; j++) {
                min[i][j] = Integer.MAX_VALUE;
                for(int a=i; a>=j-1; a--) {
                    int dist;
                    if(a-1 >= 0) {
                        if(min[a-1][j-1] == Integer.MAX_VALUE)
                            continue;
                        dist = min[a-1][j-1];
                    } else {
                        dist = 0;
                    }
                dist += minDist(arr, a, i);
                if(dist < min[i][j])
                    min[i][j] = dist;
                }
            }
        }

        return min[n-1][k];
    }

    private static int minDist(int[] arr, int start, int end) {
		int mid = (start + end) / 2;

		int sum = 0;
		for (int i = start; i <= end; i++) {
			sum += Math.abs(arr[i] - arr[mid]);
		}

		return sum;
	}


}