Given an array arr[] of size N. The task is to maximize the minimum value of the array after performing given operations. In an operation, value x can be chosen and
- A value 3 * x can be subtracted from the arr[i] element.
- A value x is added to arr[i-1]. and
- A value of 2 * x can be added to arr[i-2].
Find the maximum possible minimum element of the array after any such operations.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: 3
Explanation: The last element is chosen and x =1 can be chosen.
So 3*x gets subtracted from arr[i] and x gets added to arr[i-1] and 2*x to arr[i-2] so the array becomes {1, 2, 3, 6, 6, 3}
In the 4th index x =1 can be chosen and now the array becomes {1, 2, 5, 7, 3, 3}.
In the 3rd index x = 1 can be chosen and now the array becomes {1, 4, 6, 4, 3, 3}.
In the 2nd index again x =1 can be chosen and now the array becomes {3, 4, 3, 4, 3, 3, 3}.
Hence the maximum possible minimum value is 3.Input: arr[] = {9, 13, 167}
Output: 51
Naive Approach: This problem can be solved by checking for the possibility of maximum possible minimum value from [1, max(array)] by performing the operations from the end of the array.
Time Complexity: O(N2)
Space Complexity: O(1)
Efficient Approach: The efficient approach of this problem is based on Binary Search. Since it is based on maximizing the minimum value so by applying the binary search in the range [1, max(array)] and checking if mid is possible as a minimum element by performing the operations on the array such that every element is >=mid. Follow the steps below to solve the given problem:
- Initialize f = 1 and l = maximum element of the array and the res as INT_MIN.
- Perform binary search while f<=l
- Check if mid can be the minimum element by performing operations in the is_possible_min() function.
- In the is_possible_min() function
- Traverse from the end of the array (N-1) till index 2 and check if arr[i]<mid if it true return 0.
- Else find the extra which is 3x that can be added to arr[i-1] as x and arr[i-2] as 2x.
- If arr[0] >=mid and arr[1] >=mid return 1.
- Else return 0.
- In the is_possible_min() function
- If the is_possible_min() function returns true then mid is possible as the minimum value store the max(res, mid) in the res variable, so maximize the minimum value by moving right as f=mid +1
- Else move towards left and try if it is possible by l = mid -1.
- Print the res.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Check if mid is possible as// a minimum element after// any number of operations using// this predicate functionbool is_possible_min(vector<int> arr, int mid){ int N = arr.size(); // Traverse from the end for (int i = N - 1; i >= 2; i--) { // mid can't be minimum if (arr[i] < mid) return 0; else { // Find the 3x int extra = arr[i] - mid; // Find the x extra /= 3; // Add x to a[i-1] arr[i - 1] += extra; // Add 2x to a[i-2] arr[i - 2] += 2 * extra; } } // Check if the first two elements // are >= mid because if every element // is greater than or equal to // mid we can conclude // mid as a minimum element if (arr[0] >= mid && arr[1] >= mid) return 1; return 0;}// Function to find the// maximum possible minimum valuevoid find_maximum_min(vector<int> arr){ // Initialize f = 1 and l as the // maximum element of the array int f = 1, l = *max_element(arr.begin(), arr.end()); // Initialize res as INT_MIN int res = INT_MIN; // Perform binary search while f<=l while (f <= l) { int mid = (f + l) / 2; // Check if mid is possible // as a minimum element if (is_possible_min(arr, mid)) { // Take the max value of mid res = max(res, mid); // Try maximizing the min value f = mid + 1; } // Move left if it is not possible else { l = mid - 1; } } // Print the result cout << res << endl;}// Driver Codeint main(){ // Initialize the array vector<int> arr = { 1, 2, 3, 4, 5, 6 }; // Function call find_maximum_min(arr); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Check if mid is possible as // a minimum element after // any number of operations using // this predicate function static Boolean is_possible_min(int arr[], int mid) { int N = arr.length; // Traverse from the end for (int i = N - 1; i >= 2; i--) { // mid can't be minimum if (arr[i] < mid) return false; else { // Find the 3x int extra = arr[i] - mid; // Find the x extra /= 3; // Add x to a[i-1] arr[i - 1] += extra; // Add 2x to a[i-2] arr[i - 2] += 2 * extra; } } // Check if the first two elements // are >= mid because if every element // is greater than or equal to // mid we can conclude // mid as a minimum element if (arr[0] >= mid && arr[1] >= mid) return true; return false; } // Function to find the // maximum possible minimum value static void find_maximum_min(int arr[]) { // Initialize f = 1 and l as the // maximum element of the array int f = 1, l = Arrays.stream(arr).max().getAsInt(); // Initialize res as INT_MIN int res = Integer.MIN_VALUE; // Perform binary search while f<=l while (f <= l) { int mid = l + (f - l) / 2; // Check if mid is possible // as a minimum element if (is_possible_min(arr, mid) == true) { // Take the max value of mid res = Math.max(res, mid); // Try maximizing the min value f = mid + 1; } // Move left if it is not possible else { l = mid - 1; } } // Print the result System.out.println(res); } // Driver Code public static void main (String[] args) { // Initialize the array int arr[] = { 1, 2, 3, 4, 5, 6 }; // Function call find_maximum_min(arr); }}// This code is contributed by hrithikgarg03188. |
Python3
# python3 program for the above approachINT_MIN = -2147483647 - 1# Check if mid is possible as# a minimum element after# any number of operations using# this predicate functiondef is_possible_min(arr, mid): N = len(arr) # Traverse from the end for i in range(N-1, 1, -1): # mid can't be minimum if (arr[i] < mid): return 0 else: # Find the 3x extra = arr[i] - mid # Find the x extra //= 3 # Add x to a[i-1] arr[i - 1] += extra # Add 2x to a[i-2] arr[i - 2] += 2 * extra # Check if the first two elements # are >= mid because if every element # is greater than or equal to # mid we can conclude # mid as a minimum element if (arr[0] >= mid and arr[1] >= mid): return 1 return 0# Function to find the# maximum possible minimum valuedef find_maximum_min(arr): # Initialize f = 1 and l as the # maximum element of the array f, l = 1, max(arr) # Initialize res as INT_MIN res = INT_MIN # Perform binary search while f<=l while (f <= l): mid = (f + l) // 2 # print(is_possible_min(arr,mid)) # Check if mid is possible # as a minimum element if (is_possible_min(arr.copy(), mid)): # Take the max value of mid res = max(res, mid) # Try maximizing the min value f = mid + 1 # Move left if it is not possible else: l = mid - 1 # Print the result print(res)# Driver Codeif __name__ == "__main__": # Initialize the array arr = [1, 2, 3, 4, 5, 6] # Function call find_maximum_min(arr) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Linq;class GFG { // Check if mid is possible as // a minimum element after // any number of operations using // this predicate function static bool is_possible_min(int[] arr, int mid) { int N = arr.Length; // Traverse from the end for (int i = N - 1; i >= 2; i--) { // mid can't be minimum if (arr[i] < mid) return false; else { // Find the 3x int extra = arr[i] - mid; // Find the x extra /= 3; // Add x to a[i-1] arr[i - 1] += extra; // Add 2x to a[i-2] arr[i - 2] += 2 * extra; } } // Check if the first two elements // are >= mid because if every element // is greater than or equal to // mid we can conclude // mid as a minimum element if (arr[0] >= mid && arr[1] >= mid) return true; return false; } // Function to find the // maximum possible minimum value static void find_maximum_min(int[] arr) { // Initialize f = 1 and l as the // maximum element of the array int f = 1, l = arr.Max(); // Initialize res as INT_MIN int res = Int32.MinValue; // Perform binary search while f<=l while (f <= l) { int mid = l + (f - l) / 2; // Check if mid is possible // as a minimum element if (is_possible_min(arr, mid) == true) { // Take the max value of mid res = Math.Max(res, mid); // Try maximizing the min value f = mid + 1; } // Move left if it is not possible else { l = mid - 1; } } // Print the result Console.WriteLine(res); } // Driver Code public static void Main() { // Initialize the array int[] arr = { 1, 2, 3, 4, 5, 6 }; // Function call find_maximum_min(arr); }}// This code is contributed by Taranpreet |
Javascript
<script>// Javascript program for the above approach// Check if mid is possible as// a minimum element after// any number of operations using// this predicate functionfunction is_possible_min(arr, mid) { let N = arr.length; // Traverse from the end for (let i = N - 1; i >= 2; i--) { // mid can't be minimum if (arr[i] < mid) return 0; else { // Find the 3x let extra = arr[i] - mid; // Find the x extra = Math.floor(extra / 3); // Add x to a[i-1] arr[i - 1] += extra; // Add 2x to a[i-2] arr[i - 2] += 2 * extra; } } // Check if the first two elements // are >= mid because if every element // is greater than or equal to // mid we can conclude // mid as a minimum element if (arr[0] >= mid && arr[1] >= mid) return 1; return 0;}// Function to find the// maximum possible minimum valuefunction find_maximum_min(arr) { // Initialize f = 1 and l as the // maximum element of the array let f = 1, l = max_element(arr); // Initialize res as INT_MIN let res = Number.MIN_SAFE_INTEGER // Perform binary search while f<=l while (f <= l) { let mid = Math.ceil((f + l) / 2); // Check if mid is possible // as a minimum element if (is_possible_min(arr, mid)) { // Take the max value of mid res = Math.max(res, mid); // Try maximizing the min value f = mid + 1; } // Move left if it is not possible else { l = mid - 1; } } // Print the result document.write(res);}function max_element(ar) { return [...ar].sort((a, b) => - a + b)[0]}// Driver Code// Initialize the arraylet arr = [1, 2, 3, 4, 5, 6];// Function callfind_maximum_min(arr);// This code is contributed by saurabh_jaiswal.</script> |
Output
3
Time Complexity: O(N* log(maxval)) where maxval is the maximum element of the array. As we are using a while loop to traverse log(maxval) times as we are decrementing by floor division of 2 every traversal, and is_possible_min function will cost O (N) as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
