Given an array arr of length N, the task is to minimize its length by performing following operations:
- Remove any adjacent equal pairs, ( i.e. if arr[i] = arr[i+1]) and replace it with single instance of arr[i] + 1.
- Each operation decrements the length of the array by 1.
- Repeat the operation till no more reductions can be made.
Examples:
Input: arr = {3, 3, 4, 4, 4, 3, 3}
Output: 2
Explanation:
Merge the first two 3s and replace them by 4. Updated array: {4, 4, 4, 4, 3, 3}
Merge the first two 4s and replace them by 5. Updated array: {5, 4, 4, 3, 3}
Merge the two 4s and replace them by 5. Updated array: {5, 5, 3, 3}
Merge the two 5s and replace them by 6. Updated array: {6, 3, 3}
Merge the two 3s and replace them by 4. Updated array: {6, 4}
Hence, the minimum length of the reduced array = 2
Input: arr = {4, 3, 2, 2, 3}
Output: 2
Explanation:
Merge the two 2s and replace them by 3. Updated array: {4, 3, 3, 3}
Merge the first two 3s and replace them by 4. Updated array: {4, 4, 3}
Merge the two 4s and replace them by 5. Updated array: {5, 3}
Hence, the minimum length of the reduced array = 2
Approach: The above mentioned problem can be solved using Dynamic Programming. It can be observed that each element in the final array will be the result of the replacement of a number of elements on the corresponding segment. So our goal is to find the minimal partition of the array on segments, where each segment can be converted to a single element by a series of operations.
Let us define the following dynamic programming table state:
dp[i][j] = value of the single remaining element
when the subarray from index i to j is reduced by a series of operations or is equal to -1 when the subarray can’t be reduced to a single element.
For computing dp[i][j]:
- If i = j, dp[i][j] = a[i]
- Iterate from [i, j-1], let the traversing index be k (i <= k < j). For any k if dp[i][k] = dp[k+1][j], this means that subarray [i, j] can be divided into two parts and both the parts have same final value, so these two parts can be combined i.e. dp[i][j] = dp[i][k] + 1.
For computing minimum partitions, we will create another dp table in which the final result is stored. This table has the following state:
dp1[i] = minimum partition of subarray [1: i]
which is the minimal size of array till i after above operations are performed.
Below is the implementation of the above approach:
CPP
// C++ implementation to find the// minimum length of the array#include <bits/stdc++.h>using namespace std;// Function to find the// length of minimized arrayint minimalLength(int a[], int n){ // Creating the required dp tables int dp[n + 1][n + 1], dp1[n]; int i, j, k; // Initialising the dp table by -1 memset(dp, -1, sizeof(dp)); for (int size = 1; size <= n; size++) { for (i = 0; i < n - size + 1; i++) { j = i + size - 1; // base case if (i == j) dp[i][j] = a[i]; else { for (k = i; k < j; k++) { // Check if the two subarray // can be combined if (dp[i][k] != -1 && dp[i][k] == dp[k + 1][j]) dp[i][j] = dp[i][k] + 1; } } } } // Initialising dp1 table with max value for (i = 0; i < n; i++) dp1[i] = 1e7; for (i = 0; i < n; i++) { for (j = 0; j <= i; j++) { // Check if the subarray can be // reduced to a single element if (dp[j][i] != -1) { if (j == 0) dp1[i] = 1; // Minimal partition // of [1: j-1] + 1 else dp1[i] = min( dp1[i], dp1[j - 1] + 1); } } } return dp1[n - 1];}// Driver codeint main(){ int n = 7; int a[n] = { 3, 3, 4, 4, 4, 3, 3 }; cout << minimalLength(a, n); return 0;} |
Java
// Java implementation to find the// minimum length of the arrayimport java.util.*;class GFG{ // Function to find the// length of minimized arraystatic int minimalLength(int a[], int n){ // Creating the required dp tables int [][]dp = new int[n + 1][n + 1]; int []dp1 = new int[n]; int i, j, k; // Initialising the dp table by -1 for (i = 0; i < n + 1; i++) { for (j = 0; j < n + 1; j++) { dp[i][j] = -1; } } for (int size = 1; size <= n; size++) { for (i = 0; i < n - size + 1; i++) { j = i + size - 1; // base case if (i == j) dp[i][j] = a[i]; else { for (k = i; k < j; k++) { // Check if the two subarray // can be combined if (dp[i][k] != -1 && dp[i][k] == dp[k + 1][j]) dp[i][j] = dp[i][k] + 1; } } } } // Initialising dp1 table with max value for (i = 0; i < n; i++) dp1[i] = (int) 1e7; for (i = 0; i < n; i++) { for (j = 0; j <= i; j++) { // Check if the subarray can be // reduced to a single element if (dp[j][i] != -1) { if (j == 0) dp1[i] = 1; // Minimal partition // of [1: j-1] + 1 else dp1[i] = Math.min( dp1[i], dp1[j - 1] + 1); } } } return dp1[n - 1];} // Driver codepublic static void main(String[] args){ int n = 7; int a[] = { 3, 3, 4, 4, 4, 3, 3 }; System.out.print(minimalLength(a, n)); }}// This code contributed by Princi Singh |
Python3
# Python3 implementation to find the # minimum length of the arrayimport numpy as np# Function to find the # length of minimized array def minimalLength(a, n) : # Creating the required dp tables # Initialising the dp table by -1 dp = np.ones((n + 1,n + 1)) * -1; dp1 = [0]*n; for size in range(1, n + 1) : for i in range( n - size + 1) : j = i + size - 1; # base case if (i == j) : dp[i][j] = a[i]; else : for k in range(i,j) : # Check if the two subarray # can be combined if (dp[i][k] != -1 and dp[i][k] == dp[k + 1][j]) : dp[i][j] = dp[i][k] + 1; # Initialising dp1 table with max value for i in range(n) : dp1[i] = int(1e7); for i in range(n) : for j in range(i + 1) : # Check if the subarray can be # reduced to a single element if (dp[j][i] != -1) : if (j == 0) : dp1[i] = 1; # Minimal partition # of [1: j-1] + 1 else : dp1[i] = min( dp1[i], dp1[j - 1] + 1); return dp1[n - 1]; # Driver code if __name__ == "__main__" : n = 7; a = [ 3, 3, 4, 4, 4, 3, 3 ]; print(minimalLength(a, n)); # This code is contributed by Yash_R |
C#
// C# implementation to find the // minimum length of the array using System;class GFG{ // Function to find the // length of minimized array static int minimalLength(int []a, int n) { // Creating the required dp tables int [,]dp = new int[n + 1, n + 1]; int []dp1 = new int[n]; int i, j, k; // Initialising the dp table by -1 for (i = 0; i < n + 1; i++) { for (j = 0; j < n + 1; j++) { dp[i, j] = -1; } } for (int size = 1; size <= n; size++) { for (i = 0; i < n - size + 1; i++) { j = i + size - 1; // base case if (i == j) dp[i, j] = a[i]; else { for (k = i; k < j; k++) { // Check if the two subarray // can be combined if (dp[i, k] != -1 && dp[i, k] == dp[k + 1, j]) dp[i, j] = dp[i, k] + 1; } } } } // Initialising dp1 table with max value for (i = 0; i < n; i++) dp1[i] = (int) 1e7; for (i = 0; i < n; i++) { for (j = 0; j <= i; j++) { // Check if the subarray can be // reduced to a single element if (dp[j, i] != -1) { if (j == 0) dp1[i] = 1; // Minimal partition // of [1: j-1] + 1 else dp1[i] = Math.Min( dp1[i], dp1[j - 1] + 1); } } } return dp1[n - 1]; } // Driver code public static void Main(string[] args) { int n = 7; int []a = { 3, 3, 4, 4, 4, 3, 3 }; Console.Write(minimalLength(a, n)); } } // This code is contributed by Yash_R |
Javascript
<script>// Javascript implementation to find the// minimum length of the array// Function to find the// length of minimized arrayfunction minimalLength(a, n){ // Creating the required dp t0ables // Initialising the dp table by -1 var i, j, k; var dp = Array(n+1).fill(Array(n+1).fill(-1)); var dp1 = Array(n).fill(0); for (var size = 1; size <= n; size++) { for (i = 0; i < n - size + 1; i++) { j = i + size - 1; // base case if (i == j) dp[i][j] = a[i]; else { for (k = i; k < j; k++) { // Check if the two subarray // can be combined if (dp[i][k] != -1 && dp[i][k] == dp[k + 1][j]) dp[i][j] = dp[i][k] + 1; } } } } // Initialising dp1 table with max value for (i = 0; i < n; i++) dp1[i] = 1000000000; for (i = 0; i < n; i++) { for (j = 0; j <= i; j++) { // Check if the subarray can be // reduced to a single element if (dp[j][i] != -1) { if (j == 0) dp1[i] = 2; // Minimal partition // of [1: j-1] + 1 else dp1[i] = Math.min(dp1[i], dp1[j - 1] + 1); } } } return dp1[n - 1];}// Driver codevar n = 7;var a = [ 3, 3, 4, 4, 4, 3, 3 ];document.write(minimalLength(a, n));// This code is contributed by rrrtnx.</script> |
2
Time complexity: O(N3)
Auxiliary Space: O(N2), where N is the size of the given array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
