Shrink an array by removing triplets that satisfy given constraints
Given an integer array, shrink it by removing adjacent triplets that satisfy the given constraints and return the total number of elements in the resultant array.
A triplet (x, y, z) can only be removed if, for a given number k, the second element y of the triplet is precise k more than the first element x. The third element, z, is precise k more than the second element y. The total number of elements in the final array should be as few as possible.
For example,
Output: 3
The adjacent triplet (3, 5, 7) can be removed from the array. The resultant array is [1, 2, 8] cannot be reduced further.
Input: A[] = [-1, 0, 1, 2, 3, 4], k = 1
Output: 0
The result is 0 since we can remove all elements from the array. First, the adjacent triplet (2, 3, 4) is removed. The array is now reduced to [-1, 0, 1], which forms another valid triplet and can be removed from the array.
Note that if the adjacent triplet (1, 2, 3) is removed from the array first, we cannot reduce the resultant array [-1, 0, 4] further.
For each element x in the array, there are two alternatives:
- It does not form a triplet with any other elements in the array.
- It forms a triplet with elements
yandzin the array. To form a triplet, the difference betweeny-xandz-yshould be both equal tok. Also, if the triplet(x, y, z)is not consecutive, then to remove it from the array, all elements betweenx&yand betweeny&xshould form valid triplets and removed first.
The idea is to recursively check for all triplets and consider the combination that results in fewer elements in the final array. The algorithm can be implemented as follows in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <stdio.h> // Recursive function to shrink a given array by removing adjacent triplets from it int shrink(int arr[], int start, int end, int k) { // Base case if (start > end) { return 0; } // Keep track of the total number of elements in the resultant array int result = 0; /* Case 1: The first element, arr[start], does not form a triplet */ // Skip the first element, and recur for the next element result = 1 + shrink(arr, start + 1, end, k); // +1 since `start` is included /* Case 2: The first element, arr[start], forms a triplet with some `arr[i]` and `arr[j]` */ // Consider all triplets, and check if they can be removed from the array for (int i = start + 1; i < end; i++) { for (int j = i + 1; j <= end; j++) { /* Process current triplet: (arr[start], arr[i], arr[j]) */ // If the difference between elements of the current triplet is `k` if (arr[i] == arr[start] + k && arr[j] == arr[i] + k) { // Recursively check if all elements between `start` & `i` and // between `i` & `j` can be removed if (!shrink(arr, start + 1, i - 1, k) && !shrink(arr, i + 1, j - 1, k)) { // Recur for the next element, and update the result int n = shrink(arr, j + 1, end, k); if (result > n) { result = n; } } } } } // Return number of elements in the resultant array return result; } int main() { int arr[] = { -1, 2, 5, 8, 2, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; printf("The total number of elements in the resultant array is %d", shrink(arr, 0, n - 1, k)); return 0; } |
Output:
The total number of elements in the resultant array is 0
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
class Main { // Recursive function to shrink a given array by removing adjacent triplets from it public static int shrink(int[] arr, int start, int end, int k) { // Base case if (start > end) { return 0; } // Keep track of the total number of elements in the resultant array int result = 0; /* Case 1: The first element, arr[start], does not form a triplet */ // Skip the first element, and recur for the next element result = 1 + shrink(arr, start + 1, end, k); // +1 since `start` is included /* Case 2: The first element, arr[start], forms a triplet with some `arr[i]` and `arr[j]` */ // Consider all triplets, and check if they can be removed from the array for (int i = start + 1; i < end; i++) { for (int j = i + 1; j <= end; j++) { /* Process current triplet: (arr[start], arr[i], arr[j]) */ // If the difference between elements of the current triplet is `k` if (arr[i] == arr[start] + k && arr[j] == arr[i] + k) { // Recursively check if all elements between `start` & `i` and // between `i` & `j` can be removed if (shrink(arr, start + 1, i - 1, k) == 0 && shrink(arr, i + 1, j - 1, k) == 0) { // Recur for the next element, and update the result int n = shrink(arr, j + 1, end, k); if (result > n) { result = n; } } } } } // Return number of elements in the resultant array return result; } public static void main(String[] args) { int[] arr = { -1, 2, 5, 8, 2, 5 }; int k = 3; System.out.println("The total number of elements in the resultant array is " + shrink(arr, 0, arr.length - 1, k)); } } |
Output:
The total number of elements in the resultant array is 0
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
# Recursive function to shrink a given array by removing adjacent triplets from it def shrink(arr, start, end, k): # base case if start > end: return 0 ''' Case 1: The first element, arr[start], does not form a triplet ''' # Skip the first element, and recur for the next element result = 1 + shrink(arr, start + 1, end, k) # +1 since `start` is included ''' Case 2: The first element, arr[start], forms a triplet with some `arr[i]` and `arr[j]` ''' # Consider all triplets, and check if they can be removed from the array for i in range(start + 1, end): for j in range(i + 1, end + 1): ''' Process current triplet: (arr[start], arr[i], arr[j]) ''' # If the difference between elements of the current triplet is `k` if arr[i] == arr[start] + k and arr[j] == arr[i] + k: # Recursively check if all elements between `start` & `i` and # between `i` & `j` can be removed if not shrink(arr, start + 1, i - 1, k)\ and not shrink(arr, i + 1, j - 1, k): # Recur for the next element, and update the result n = shrink(arr, j + 1, end, k) result = min(result, n) # Return number of elements in the resultant array return result if __name__ == '__main__': arr = [-1, 2, 5, 8, 2, 5] k = 3 print('The total number of elements in the resultant array is', shrink(arr, 0, len(arr) - 1, k)) |
Output:
The total number of elements in the resultant array is 0
The time complexity of the above solution is exponential as several subproblems are recalculated over and over again, i.e., it exhibits overlapping subproblems. The repeated subproblems can be easily seen by drawing a recursion tree for larger values of n. The problem also has an optimal substructure since it can be recursively broken down into smaller subproblems.
The problems having an optimal substructure and overlapping subproblems can be solved using dynamic programming. The dynamic programming solution is left as an exercise to readers (Hint – save solutions to the subproblems in a hash table).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)