# Clustering/Partitioning an array such that sum of square differences is minimum

Given an array of n numbers and a number k. We need to divide the array into k partitions (clusters) of same or different length. For a given k, there can be one or more ways to make clusters (partitions). We define a function Cost(i) for the cluster, as the square of the difference between its first and last element. If the current cluster is , where is the length of current cluster, then .
Amongst all the possible kinds of partitions, we have to find the partition that will minimize the function, Examples :

```Input : arr[] = {1, 5, 8, 10}
k = 2
Output : 20
Explanation :
Consider clustering 4 elements 1, 5, 8, 10
into 2 clusters. There are three options:
1. S1 = 1, S2 = 5, 8, 10, with total cost + = 25.
2. S1 = 1, 5, S2 = 8, 10, with total cost + = 20.
3. S1 = 1, 5, 8, S2 = 10, with total cost + = 49.
So, the optimal clustering is the second one,
so the output of the above problem is 20.

Input : arr[] = {5, 8, 1, 10}
k = 3
Output : 20
Explanation :
The three partitions are {5, 8}, {1} and {10}
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

To solve the problem, we assume that we have k slabs. We have to insert them in some k different positions in the array, which will give us the required partition scheme, and the one having minimum value for f(x) will be the answer.

Naive solution:

If we solve the above problem by the naive method, we would simply take all the possibilities and compute the minimum.

div class="responsive-tabs">

## C++

 `// C++ program to find minimum cost k partitions ` `// of array. ` `#include ` `using` `namespace` `std; ` ` `  `// Initialize answer as infinite. ` `const` `int` `inf = 1000000000; ` `int` `ans = inf; ` ` `  `// function to generate all possible answers. ` `// and comute minimum of all costs. ` `// i   --> is index of previous partition ` `// par --> is current number of partitions ` `// a[] and n --> Input array and its size ` `// current_ans --> Cost of partitions made so far. ` `void` `solve(``int` `i, ``int` `par, ``int` `a[], ``int` `n, ` `                  ``int` `k, ``int` `current_ans) ` `{ ` `    ``// If number of partitions is more than k ` `    ``if` `(par > k) ` `        ``return``; ` ` `  `    ``// If we have mad k partitions and have ` `    ``// reached last element ` `    ``if` `(par==k && i==n-1) ` `    ``{ ` `        ``ans = min(ans, current_ans); ` `        ``return``; ` `    ``} ` ` `  `    ``// 1) Partition array at different points ` `    ``// 2) For every point, increase count of  ` `    ``//    partitions, "par" by 1. ` `    ``// 3) Before recursive call, add cost of  ` `    ``//    the partition to current_ans ` `    ``for` `(``int` `j=i+1; j

## Java

 `// Java program to find minimum cost k partitions ` `// of array. ` `import` `java.io.*; ` ` `  `class` `GFG ` `{ ` `    ``// Initialize answer as infinite. ` `    ``static` `int` `inf = ``1000000000``; ` `    ``static` `int` `ans = inf; ` `     `  `    ``// function to generate all possible answers. ` `    ``// and comute minimum of all costs. ` `    ``// i --> is index of previous partition ` `    ``// par --> is current number of partitions ` `    ``// a[] and n --> Input array and its size ` `    ``// current_ans --> Cost of partitions made so far. ` `    ``static` `void` `solve(``int` `i, ``int` `par, ``int` `a[], ``int` `n, ` `                               ``int` `k, ``int` `current_ans) ` `    ``{ ` `        ``// If number of partitions is more than k ` `        ``if` `(par > k) ` `            ``return``; ` `     `  `        ``// If we have mad k partitions and have ` `        ``// reached last element ` `        ``if` `(par == k && i == n - ``1``) ` `        ``{ ` `            ``ans = Math.min(ans, current_ans); ` `            ``return``; ` `        ``} ` `     `  `        ``// 1) Partition array at different points ` `        ``// 2) For every point, increase count of  ` `        ``// partitions, "par" by 1. ` `        ``// 3) Before recursive call, add cost of  ` `        ``// the partition to current_ans ` `        ``for` `(``int` `j = i + ``1``; j < n; j++) ` `            ``solve(j, par + ``1``, a, n, k, current_ans + ` `                 ``(a[j] - a[i + ``1``]) * (a[j] - a[i + ``1``])); ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `k = ``2``; ` `        ``int` `a[] = {``1``, ``5``, ``8``, ``10``}; ` `        ``int` `n = a.length; ` `        ``solve(-``1``, ``0``, a, n, k, ``0``); ` `        ``System.out.println(ans); ` `         `  `    ``} ` `}  ` ` `  `// This code is contributed by vt_m. `

## Python3

 `# Python3 program to find minimum  ` `# cost k partitions of array. ` ` `  `# Initialize answer as infinite.  ` `inf ``=` `1000000000` `ans ``=` `inf ` ` `  `# function to generate all possible answers.  ` `# and comute minimum of all costs.  ` `# i --> is index of previous partition  ` `# par --> is current number of partitions  ` `# a[] and n --> Input array and its size  ` `# current_ans --> Cost of partitions made so far. ` `def` `solve(i, par, a, n, k, current_ans): ` `     `  `    ``# If number of partitions is more than k ` `    ``if` `(par > k): ` `        ``return` `0` `         `  `    ``# If we have mad k partitions and  ` `    ``# have reached last element ` `    ``global` `ans ` `    ``if` `(par ``=``=` `k ``and` `i ``=``=` `n ``-` `1``): ` `        ``ans ``=` `min``(ans, current_ans) ` `        ``return` `0` ` `  `    ``# 1) Partition array at different points  ` `    ``# 2) For every point, increase count of  ` `    ``# partitions, "par" by 1.  ` `    ``# 3) Before recursive call, add cost of  ` `    ``# the partition to current_ans  ` `    ``for` `j ``in` `range``(i ``+` `1``, n): ` `        ``solve(j, par ``+` `1``, a, n, k, current_ans ``+`  `             ``(a[j] ``-` `a[i ``+` `1``]) ``*` `(a[j] ``-` `a[i ``+` `1``])) ` ` `  `# Driver code  ` `k ``=` `2` `a ``=` `[``1``, ``5``, ``8``, ``10``] ` `n ``=` `len``(a) ` `solve(``-``1``, ``0``, a, n, k, ``0``) ` `print``(ans) ` ` `  `# This code is contributed by sahilshelangia `

## C#

 `// C# program to find minimum ` `// cost k partitions of array. ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``// Initialize answer as infinite. ` `    ``static` `int` `inf = 1000000000; ` `    ``static` `int` `ans = inf; ` `     `  `    ``// function to generate all possible answers. ` `    ``// and comute minimum of all costs. ` `    ``// i --> is index of previous partition ` `    ``// par --> is current number of partitions ` `    ``// a[] and n --> Input array and its size ` `    ``// current_ans --> Cost of partitions made so far. ` `    ``static` `void` `solve(``int` `i, ``int` `par, ``int` `[]a, ` `                      ``int` `n, ``int` `k, ``int` `current_ans) ` `    ``{ ` `        ``// If number of partitions is more than k ` `        ``if` `(par > k) ` `            ``return``; ` `     `  `        ``// If we have mad k partitions and ` `        ``// have reached last element ` `        ``if` `(par == k && i == n - 1) ` `        ``{ ` `            ``ans = Math.Min(ans, current_ans); ` `            ``return``; ` `        ``} ` `     `  `        ``// 1) Partition array at different points ` `        ``// 2) For every point, increase count of  ` `        ``// partitions, "par" by 1. ` `        ``// 3) Before recursive call, add cost of  ` `        ``// the partition to current_ans ` `        ``for` `(``int` `j = i + 1; j < n; j++) ` `            ``solve(j, par + 1, a, n, k, current_ans + ` `                 ``(a[j] - a[i + 1]) * (a[j] - a[i + 1])); ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``int` `k = 2; ` `        ``int` `[]a = {1, 5, 8, 10}; ` `        ``int` `n = a.Length; ` `        ``solve(-1, 0, a, n, k, 0); ` `        ``Console.Write(ans); ` `    ``} ` `}  ` ` `  `// This code is contributed by nitin mittal. `

## PHP

 ` is index of previous partition ` `// par --> is current number of partitions ` `// a[] and n --> Input array and its size ` `// current_ans --> Cost of partitions made so far. ` `function` `solve(``\$i``, ``\$par``, &``\$a``, ``\$n``, ``\$k``, ``\$current_ans``) ` `{ ` `    ``global` `\$inf``, ``\$ans``; ` `     `  `    ``// If number of partitions is  ` `    ``// more than k ` `    ``if` `(``\$par` `> ``\$k``) ` `        ``return``; ` ` `  `    ``// If we have mad k partitions and  ` `    ``// have reached last element ` `    ``if` `(``\$par` `== ``\$k` `&& ``\$i` `== ``\$n` `- 1) ` `    ``{ ` `        ``\$ans` `= min(``\$ans``, ``\$current_ans``); ` `        ``return``; ` `    ``} ` ` `  `    ``// 1) Partition array at different points ` `    ``// 2) For every point, increase count of  ` `    ``//    partitions, "par" by 1. ` `    ``// 3) Before recursive call, add cost of  ` `    ``//    the partition to current_ans ` `    ``for` `(``\$j` `= ``\$i` `+ 1; ``\$j` `< ``\$n``; ``\$j``++) ` `        ``solve(``\$j``, ``\$par` `+ 1, ``\$a``, ``\$n``, ``\$k``, ``\$current_ans` `+ ` `                           ``(``\$a``[``\$j``] - ``\$a``[``\$i` `+ 1]) *  ` `                           ``(``\$a``[``\$j``] - ``\$a``[``\$i` `+ 1])); ` `} ` ` `  `// Driver code ` `\$k` `= 2; ` `\$a` `= ``array``(1, 5, 8, 10); ` `\$n` `= sizeof(``\$a``); ` `solve(-1, 0, ``\$a``, ``\$n``, ``\$k``, 0); ` `echo` `\$ans` `. ````" "````; ` ` `  `// This code is contributed by ita_c ` `?> `

Output:

```20
```

Time Complexity: Its clear that the above algorithm has Time Complexity of .

Dynamic Programming:

We create a table dp[n+1][k+1] table and initialize all values as infinite.

```dp[i][j] stores optimal partition cost
for arr[0..i-1] and j partitions.
```

Let us compute the value of dp[i][j]. we take an index m, such that m < i, and put a partition next to that position such that there is no slab in between the indices i and m. It can be seen simply that answer to the current scenario is dp[m][j-1] + (a[i-1]-a[m])*(a[i-1]-a[m]), where the first term signifies the minimum f(x) till the element with j-1 partitions and the second one signifies the cost of current cluster. So we will take the minimum of all the possible indices m and dp[i][j] will be assigned the minimum amongst them.

## C++

 `// C++ program to find minimum cost k partitions ` `// of array. ` `#include ` `using` `namespace` `std; ` `const` `int` `inf = 1000000000; ` ` `  `// Returns minimum cost of partitioning a[] in ` `// k clusters. ` `int` `minCost(``int` `a[], ``int` `n, ``int` `k) ` `{ ` `    ``// Create a dp[][] table and initialize ` `    ``// all values as infinite. dp[i][j] is ` `    ``// going to store optimal partition cost ` `    ``// for arr[0..i-1] and j partitions ` `    ``int` `dp[n+1][k+1]; ` `    ``for` `(``int` `i=0; i<=n; i++) ` `        ``for` `(``int` `j=0;j<=k;j++) ` `            ``dp[i][j] = inf; ` ` `  `    ``// Fill dp[][] in bottom up manner ` `    ``dp = 0; ` ` `  `    ``// Current ending position (After i-th ` `    ``// iteration result for a[0..i-1] is computed. ` `    ``for` `(``int` `i=1;i<=n;i++) ` ` `  `        ``// j is number of partitions ` `        ``for` `(``int` `j=1;j<=k;j++) ` ` `  `            ``// Picking previous partition for ` `            ``// current i. ` `            ``for` `(``int` `m=i-1;m>=0;m--) ` `                ``dp[i][j] = min(dp[i][j], dp[m][j-1] + ` `                          ``(a[i-1]-a[m])*(a[i-1]-a[m])); ` ` `  ` `  `    ``return` `dp[n][k]; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `k = 2; ` `    ``int` `a[] = {1, 5, 8, 10}; ` `    ``int` `n = ``sizeof``(a)/``sizeof``(a); ` `    ``cout << minCost(a, n, k) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java program to find minimum cost  ` `// k partitions of array. ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `    ``static` `int` `inf = ``1000000000``; ` `     `  `    ``// Returns minimum cost of partitioning  ` `    ``// a[] in k clusters. ` `    ``static` `int` `minCost(``int` `a[], ``int` `n, ``int` `k) ` `    ``{ ` `        ``// Create a dp[][] table and initialize ` `        ``// all values as infinite. dp[i][j] is ` `        ``// going to store optimal partition cost ` `        ``// for arr[0..i-1] and j partitions ` `        ``int` `dp[][] = ``new` `int``[n + ``1``][k + ``1``]; ` `        ``for` `(``int` `i = ``0``; i <= n; i++) ` `            ``for` `(``int` `j = ``0``; j <= k; j++) ` `                ``dp[i][j] = inf; ` `     `  `        ``// Fill dp[][] in bottom up manner ` `        ``dp[``0``][``0``] = ``0``; ` `     `  `        ``// Current ending position (After i-th ` `        ``// iteration result for a[0..i-1] is computed. ` `        ``for` `(``int` `i = ``1``; i <= n; i++) ` `     `  `            ``// j is number of partitions ` `            ``for` `(``int` `j = ``1``; j <= k; j++) ` `     `  `                ``// Picking previous partition for ` `                ``// current i. ` `                ``for` `(``int` `m = i - ``1``; m >= ``0``; m--) ` `                    ``dp[i][j] = Math.min(dp[i][j], dp[m][j - ``1``] + ` `                              ``(a[i - ``1``] - a[m]) * (a[i - ``1``] - a[m])); ` `     `  `     `  `        ``return` `dp[n][k]; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `k = ``2``; ` `        ``int` `a[] = {``1``, ``5``, ``8``, ``10``}; ` `        ``int` `n = a.length; ` `        ``System.out.println(minCost(a, n, k)); ` `             `  `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## C#

 `// C# program to find minimum cost  ` `// k partitions of array. ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``static` `int` `inf = 1000000000; ` `     `  `    ``// Returns minimum cost of partitioning  ` `    ``// a[] in k clusters. ` `    ``static` `int` `minCost(``int` `[]a, ``int` `n, ``int` `k) ` `    ``{ ` `         `  `        ``// Create a dp[][] table and initialize ` `        ``// all values as infinite. dp[i][j] is ` `        ``// going to store optimal partition cost ` `        ``// for arr[0..i-1] and j partitions ` `        ``int` `[,]dp = ``new` `int``[n + 1,k + 1]; ` `        ``for` `(``int` `i = 0; i <= n; i++) ` `            ``for` `(``int` `j = 0; j <= k; j++) ` `                ``dp[i,j] = inf; ` `     `  `        ``// Fill dp[][] in bottom ` `        ``// up manner ` `        ``dp[0,0] = 0; ` `     `  `        ``// Current ending position  ` `        ``// (After i-th iteration  ` `        ``// result for a[0..i-1] ` `        ``// is computed. ` `        ``for` `(``int` `i = 1; i <= n; i++) ` `     `  `            ``// j is number of partitions ` `            ``for` `(``int` `j = 1; j <= k; j++) ` `     `  `                ``// Picking previous ` `                ``// partition for ` `                ``// current i. ` `                ``for` `(``int` `m = i - 1; m >= 0; m--) ` `                    ``dp[i,j] = Math.Min(dp[i,j], ` `                                 ``dp[m,j - 1] + ` `                               ``(a[i - 1] - a[m]) *  ` `                               ``(a[i - 1] - a[m])); ` `     `  `     `  `        ``return` `dp[n,k]; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``int` `k = 2; ` `        ``int` `[]a = {1, 5, 8, 10}; ` `        ``int` `n = a.Length; ` `        ``Console.Write(minCost(a, n, k)); ` `             `  `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal `

Output:

```20
```

Time Complexity: Having the three simple loops, the complexity of the above algorithm is .