Divide an Array Into Subarrays With Minimum Cost in Java
In this tutorial, we going to divide an array into subarrays with minimum cost in java. The aim is to determine the lowest cost that can be incurred to divide an array containing N integers from the range [1, N] and an integer K into non-empty subarrays. It may be done by taking into account the following conditions:
1. In the event that the subarray has no unique elements, the cost is K.
2. If not, the cost is equal to K plus the sum of the frequencies of all elements that repeat.
Given the array of size N, the objective is to use this technique to partition the array nums[] into groups of size K: The first group of the array is made up of the first K elements, the second group is made up of the next K elements, and so on. Every element can only be a member of one group. Use 0 to complete the group if there are no more K elements in the array for the last group.
Examples:
Example 1:
Input: arr[] = {1, 2, 3, 1, 2, 3}, K = 2
Output: 4
Explanation: The least amount of money is produced by splitting the array into the subarrays {1, 2, 3} and {1, 2, 3} since none of the subarrays have any repeating elements. Since there will be at least one repeating element in one subarray, the cost of all other splits will be higher. Thus, four is the lowest that can be charged.
Example 2:
Input: arr[] = {1, 2, 1, 1, 1}, K = 2
Output: 6
Example 3:
Input: nums = [1, 2, 3, 12]
Output: 6
Explanation: The best possible way to form 3 subarrays is: [1], [2], and [3, 12] at a totalcost of 1 + 2 + 3 = 6.
The other possible ways to form 3 subarrays are:
[1], [2, 3], and [12] at a total cost of 1 + 2 + 12 = 15.
[1, 2], [3], and [12] at a total cost of 1 + 3 + 12 = 16.
Example 4:
Input: nums = [5, 4, 3,]
Output: 12
Explanation: The best possible way to form 3 subarrays is: [5], [4], and [3] at a totalcost of 5 + 4 + 3 = 12.
It can be shown that 12 is the minimum cost achievable.
Example 5:
Input: nums = [10, 3, 1, 1]
Output: 12
Explanation: The best possible way to form 3 subarrays is: [10, 3], [1], and [1] at a totalcost of 10 + 1 + 1 = 12.
It can be shown that 12 is the minimum cost achievable.
Example 6:
Input: arr[] = { 2, 3, 4, 1 }, K = 3
Output: 11
Explanation:
Split the array arr[] into K(= 3) subsets { { 4, 1 }, { 2 }, { 3 } }
Total cost of 1st subset = 4 * 1 + 1 * 2 = 6
Total cost of 2nd subset = 2 * 1 = 2
Total cost of 3rd subset = 3 * 1 = 3
Therefore, the total cost of K(= 3) subsets is 6 + 2 + 3 = 11.
Example 7:
Input: arr[] = { 9, 20, 7, 8 }, K=2
Output: 59
Explanation:
Dividing the array arr[] into K(= 3) subsets { { 20, 8 }, { 9, 7 } }
Total cost of 1st subset = 20 * 1 + 8 * 2 = 36
Total cost of 2nd subset = 9 * 1 + 7 * 2 = 23
Therefore, the total cost of K(= 3) subsets is 36 + 23 = 59
Approach 1: Using dynamic programming
ALGORITHM:
Step 1: Use INT_MAX at all indices to initialize an array of length N, called dp[].
Step 2: Set the array's first element's initial value to zero.
Step 3: For any index i the array dp[i] represents the minimum cost to divide the array into subarrays from 0 to i.
Step 4: Compute the minimum cost of every index, i to N, for each index i.
Step 5: For each of the array's elements, repeat these steps.
Step 6: Return the last elements of dp[] to get the minimum cost of splitting the array.
Filename: SplitElement.java
import java.util.*; public class SplitElement { // Function to find the // minimum cost of splitting // the array into subarrays static long findMinCost(int[] a, int k, int n) { // Get the maximum element int max_ele = Arrays.stream(a).max().getAsInt(); // dp[] will store the minimum cost // upto index i long[] dp = new long[n + 1]; // Initialize the result array for (int i = 1; i <= n; ++i) dp[i] = Integer.MAX_VALUE; // Initialise the first element dp[0] = 0; for (int i = 0; i < n; ++i) { // Create the frequency array int[] freq = new int[max_ele + 1]; for (int j = i; j < n; ++j) { // Update the frequency freq[a[j]]++; int cost = 0; // Counting the cost of // the duplicate element for (int x = 0; x <= max_ele; ++x) { cost += (freq[x] == 1)? 0: freq[x]; } // Minimum cost of operation // from 0 to j dp[j + 1] = Math.min(dp[i] + cost + k, dp[j + 1]); } } // Total cost of the array return dp[n]; } public static void main(String[] args) { int[] arr = {1, 2, 1, 1, 1}; // Given cost K int K = 2; int n = arr.length; System.out.print(findMinCost(arr, K, n)); } }
Output:
6
Time complexity: The time complexity of the program is O(N^3).
Space complexity: The space complexity of the program is O(N).
Approach 2: Using selection sort algorithm
ALGORITHM:
Step 1: Determine an elementary approach of the lowest possible cost that involves first sorting the array of integers ({nums}) in ascending order.
Step 2: Re-arrange the items throughout the sorting process so that the smallest values start at the beginning of the array.
Step 3: Retrieve the first three items of the array by the algorithm after it has been sorted, since they correspond to the three values with the smallest values.
Step 4: Determine the minimum cost ultimately by adding these three components together and returning the result.
Filename: SmallestElement.java
public class SmallestElement { public static void main(String[] args) { int[] nums = {5, 10, 3, 7, 2}; SmallestElement smallestelement = new SmallestElement(); int minimumCost = smallestelement.minimumCost(nums); System.out.println("Minimum Cost: " + minimumCost); } public int minimumCost(int[] nums) { if (nums.length < 3) { // Handle case where array has less than three elements return -1; // Or handle it according to your application logic } int a = nums[0], b = 100, c = 100; for (int i = 1; i < nums.length; ++i) { if (nums[i] < b) { c = b; b = nums[i]; } else if (nums[i] < c) { c = nums[i]; } } return a + b + c; } }
Output:
Minimum Cost: 10
Time complexity: The time complexity of the program is O(n).
Space complexity: The space complexity of the program is O(1).
Approach 3: Using greedy technique
ALGORITHM:
Step 1: Arrange the given array in a descending order.
Step 2: Create a variable called totalCost and set its initial value to the lowest amount required to divide the array into K subgroups.
step 3: Set up a variable, let's say X, to hold the element's location within a subset.
step 4: Use variable i to iterate across the range [1, N]. For each ith operation, update i = i + K, X += 1, and increase the value of totalCost by ((arr[i]+...+ arr[i + K]) * X).
step 5: Lastly, output the totalCost value.
Filename: MinimumCost.java
import java.util.*; public class MinimumCost { // reverses an array static void reverse(int a[], int n) { int i, k, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } } // Function to find the minimum cost to // split array into K subsets static int getMinCost(int[] arr, int n, int k) { // Sort the array in descending order Arrays.sort(arr); reverse(arr, n); // Stores minimum cost to split // the array into K subsets int min_cost = 0; // Stores position of // elements of a subset int X = 0; // Iterate over the range [1, N] for (int i = 0; i < n; i += k) { // Calculate the cost to select // X-th element of every subset for (int j = i; j < i + k && j < n; j++) { // Update min_cost min_cost += arr[j] * (X + 1); } // Update X X++; } return min_cost; } public static void main(String[] args) { int arr[] = { 9, 20, 7, 8 }; int K = 2; int N = arr.length; // Function call System.out.println( getMinCost(arr, N, K)); } }
Output:
59
Time complexity: The time complexity of the program is O(N*log(N)).
Space complexity: The space complexity of the program is O(1).