Truncate an integer array such that `2×min` becomes more than `max`
Given an array of positive integers, truncate it such that 2×min becomes more than max, and the total number of removals is minimal. The min and max are the minimum and the maximum elements in the array, respectively. The elements can be removed either from the start or end of the array if the above condition does not meet.
For example,
Output: The minimum number of removals is 4
The truncated array is [7, 5, 9] where 9 < 2 × 5.
Input: [4, 2, 6, 4, 9]
Output: The minimum number of removals is 3
The truncated array is [6, 4] where 6 < 2 × 4.
1. Brute-Force Solution
The idea is to recursively find the optimal value by removing elements from each side of the array and choosing the end, leading to fewer removals. Following is the C++, Java, and Python program that demonstrates it:
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 |
#include <iostream> #include <algorithm> using namespace std; int findMin(int arr[], int low, int high) { // base case if (low > high) { return 0; } // find the minimum and the maximum elements in array `arr[low…high]` int min = *min_element(arr + low, arr + high + 1); int max = *max_element(arr + low, arr + high + 1); // if the array is not balanced if (2 * min <= max) { // remove the leftmost element from the array, and recur with the // remaining elements int L = 1 + findMin(arr, low + 1, high); // remove the rightmost element from the array, and recur with the // remaining elements int R = 1 + findMin(arr, low, high - 1); // return the minimum of two return std::min(L, R); } // we reach here if the array is already balanced return 0; } int main() { int arr[] = { 4, 2, 6, 4, 9 }; int n = end(arr) - begin(arr); cout << "The minimum number of removals is " << findMin(arr, 0, n - 1) << endl; return 0; } |
Output:
The minimum number of removals is 3
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 |
import java.util.Arrays; import java.util.Comparator; import java.util.List; class Main { public static int findMin(List<Integer> input, int low, int high) { // base case if (low > high) { return 0; } // find the minimum element in array `input[low…high]` int min = input.subList(low, high + 1) .stream() .min(Comparator.naturalOrder()) .get(); // find the maximum element in array `input[low…high]` int max = input.subList(low, high + 1) .stream() .max(Comparator.naturalOrder()) .get(); // if the array is not balanced if (2 * min <= max) { // remove the leftmost element from the array, and recur with the // remaining elements int L = 1 + findMin(input, low + 1, high); // remove the rightmost element from the array, and recur with the // remaining elements int R = 1 + findMin(input, low, high - 1); // return the minimum of two return Integer.min(L, R); } // we reach here if the array is already balanced return 0; } public static void main(String[] args) { List<Integer> input = Arrays.asList(4, 2, 6, 4, 9); System.out.println("The minimum number of removals is " + findMin(input, 0, input.size() - 1)); } } |
Output:
The minimum number of removals is 3
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 |
def findMin(arr, low, high): # base case if low > high: return 0 # find the minimum and the maximum elements in array `arr[low…high]` # and check if the array is not balanced subarr = arr[low:high+1] if 2 * min(subarr) <= max(subarr): # remove the leftmost element from the array, and recur with the # remaining elements L = 1 + findMin(arr, low + 1, high) # remove the rightmost element from the array, and recur with the # remaining elements R = 1 + findMin(arr, low, high - 1) # return the minimum of two return min(L, R) # we reach here if the array is already balanced return 0 if __name__ == '__main__': arr = [4, 2, 6, 4, 9] print('The minimum number of removals is', findMin(arr, 0, len(arr) - 1)) |
Output:
The minimum number of removals is 3
The time complexity of the above solution is O(2n), where n is the size of the input. The auxiliary space required by the program is O(n2) for recursion (call stack).
2. Dynamic Programming Solution
On drawing a recursion tree for the above solution, we can easily see that each subproblem gets repeated several times. The problem satisfies both optimal substructure and overlapping subproblems properties of dynamic programming, so the subproblem solutions can be derived using memoization or in a bottom-up manner.
Following is the dynamic programming solution in C++, Java, and Python, that iteratively build up a table of values T[i][j] to prevent redundant calculations of the same value:
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 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; int findMin(int arr[], int n) { // base case if (n == 0) { return 0; } // create a table for saving solutions to subproblems vector<vector<int>> T(n, vector<int>(n, 0)); // fill the table diagonally for (int diagonal = 0; diagonal < n; diagonal++) { for (int i = 0, j = diagonal; j < n; i++, j++) { // find the minimum and the maximum elements in subarray `arr[i…j]` int min = *min_element(arr + i, arr + j + 1); int max = *max_element(arr + i, arr + j + 1); // if subarray `arr[i…j]` is not balanced, choose the minimum // removals among subarray `arr[i…j-1]` and `arr[i-1…j]` if (2 * min <= max) { T[i][j] = std::min(1 + T[i][j - 1], 1 + T[i + 1][j]); } } } // the top-rightmost element in the table stores the result return T[0][n - 1]; } int main() { int arr[] = { 4, 2, 6, 4, 9 }; int n = end(arr) - begin(arr); cout << "The minimum number of removals is " << findMin(arr, n) << endl; return 0; } |
Output:
The minimum number of removals is 3
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 |
import java.util.Arrays; import java.util.Comparator; import java.util.List; class Main { public static int findMin(List<Integer> input) { int n = input.size(); // base case if (n == 0) { return 0; } // create a table for saving solutions to subproblems int[][] T = new int[n][n]; // fill the table diagonally for (int diagonal = 0; diagonal < n; diagonal++) { for (int i = 0, j = diagonal; j < n; i++, j++) { // find the minimum element in subarray `input[i…j]` int min = input.subList(i, j + 1) .stream() .min(Comparator.naturalOrder()) .get(); // find the maximum element in subarray `input[i…j]` int max = input.subList(i, j + 1) .stream() .max(Comparator.naturalOrder()) .get(); // if subarray `input[i…j]` is not balanced, choose the minimum // removals among subarray `input[i…j-1]` and `input[i-1…j]` if (2 * min <= max) { T[i][j] = Integer.min(1 + T[i][j - 1], 1 + T[i + 1][j]); } } } // the top-rightmost element in the table stores the result return T[0][n - 1]; } public static void main(String[] args) { List<Integer> input = Arrays.asList(4, 2, 6, 4, 9); System.out.println("The minimum number of removals is " + findMin(input)); } } |
Output:
The minimum number of removals is 3
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 |
def findMin(arr): # base case if not arr: return 0 # create a table for saving solutions to subproblems T = [[0] * len(arr) for _ in range(len(arr))] # fill the table diagonally for diagonal in range(len(arr)): i = 0 for j in range(diagonal, len(arr)): # find the minimum and the maximum elements in subarray `arr[i…j]` # if subarray `arr[i…j]` is not balanced, choose the minimum # removals among subarray `arr[i…j-1]` and `arr[i-1…j]` if 2 * min(arr[i:j+1]) <= max(arr[i:j+1]) and j - 1 >= 0 and i + 1 < len(arr): T[i][j] = min(1 + T[i][j - 1], 1 + T[i + 1][j]) i += 1 # the top-rightmost element in the table stores the result return T[0][-1] if __name__ == '__main__': arr = [4, 2, 6, 4, 9] print('The minimum number of removals is', findMin(arr)) |
Output:
The minimum number of removals is 3
The above solution takes O(n3) time and O(n2) extra space. Refer to the following post for another approach to solve this problem that doesn’t require any extra space, handles negative numbers, and offers better runtime than the dynamic programming algorithm.
Find minimum removals required in an array to satisfy given constraints
Find minimum removals required in an array to satisfy given constraints
Find the minimum and maximum element in an array using Divide and Conquer
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 :)