C++ program to remove the smallest element from both sides so that the 2* minimum value is greater than the maximum value

The problem involves removing elements from either side of a list of integers in such a way that 2*min is greater than max.

vector<int> arr = {250, 10, 11, 12, 19, 200};
res = solve(arr);

We can use brute force methods. We can try all possible satisfactions and find the longest subarray that satisfies the condition 2*min > max. We can also use dynamic programming methods to try all possible excessive and unwanted subarray combinations.

Example (using vector ADT)

Suppose we have an array, such as "[250, 10, 11, 12, 19, 200]". To get the best solution we need to remove elements [250, 200] to form an array [10, 11, 12, 19] where min is 10 and max is 19. Therefore 2*10 > 19. We are printing from an array, so the output is 2.

The following is a C program that describes how to remove a minimum number of elements from an array such that twice the minimum value is greater than the maximum value -

#include <iostream>
#include <vector>
using namespace std;
int solve(vector<int> arr) {
   int startIndex = 0, endIndex = 0;
   bool foundAnAnswer = false;
   for (int start=0; start<arr.size(); start++) {
      int min = INT32_MAX, max = INT32_MIN;
      for (int end=start; end<arr.size(); end++) {
         if (arr[end] < min) min = arr[end];
         if (arr[end] > max) max = arr[end];
         if (2*min <= max) break;
         if (end - start > endIndex - startIndex || !foundAnAnswer) {
            startIndex = start;
            endIndex = end;
            foundAnAnswer = true;
         }
      }
   }
   if (!foundAnAnswer) return arr.size();
   return (arr.size() - (endIndex - startIndex + 1));
}
int main() {
   vector<int> arr = {250, 10, 11, 12, 19, 200};
   cout << solve(arr);
   return 0;
}

Output

2

Example (not using vector ADT)

The following is a C program describing how to remove the minimum number of elements from an array such that twice the minimum value is greater than the maximum value, but without using Vector ADT -

#include <iostream>
using namespace std;
int min(int a, int b) {return (a < b)? a : b;}
int min(int arr[], int low, int high)
   {
      int minimum = arr[low];
      for (int i=low+1; i<=high; i++)
      if (minimum > arr[i])
         minimum = arr[i];
      return minimum;
   }
int max(int arr[], int low, int high)
   {
      int maximum = arr[low];
      for (int i=low+1; i<=high; i++)
      if (maximum < arr[i])
         maximum = arr[i];
      return maximum;
   }
int minimum_removals(int arr[], int low, int high)
   {
      if (low >= high)
      return 0;
      int m1 = min(arr, low, high);
      int m2 = max(arr, low, high);
      if (2*m1 > m2)
      return 0;
      return min(minimum_removals(arr, low+1, high), minimum_removals(arr, low, high-1)) + 1;
   }
int main()
   {
      int arr[] = {12, 45, 32, 88, 100};
      int n = sizeof(arr)/sizeof(arr[0]);
      cout << minimum_removals(arr, 0, n-1);
      return 0;
   }

Output

3

in conclusion

Here we use a brute force method to find the longest subarray. Other possible solutions might include checking every possible subarray by repeatedly popping elements from both sides and other methods. Nonetheless, their implementation is labor intensive and less optimized. The time complexity here is O(n^2) because we have already iterated through all sub-arrays.

The above is the detailed content of C++ program to remove the smallest element from both sides so that the 2* minimum value is greater than the maximum value. For more information, please follow other related articles on the PHP Chinese website!