Given an array Arr[ ] of N integers where 1 ≤ N ≤ 105. The task is to choose any number of elements from the array such that:
- For each i ( 0≤ i ≥ N-2 ), at least one of the ith and (i+1)th elements must be chosen.
- Find the maximum possible median of integers from the subsequence of the array thus formed.
Examples:
Input: N = 6, Arr[ ] = { 2, 1, 2, 1, 1, 10 }
Output: 2
Explanation : Choosing arr[0], arr[2], arr[4] and arr[5] makes the subsequence as { 2, 2, 1, 10 } giving median as 2 which is maximum possible. Also note that the condition that atleast one of the two consecutive elements must be chosen is satisfied.Input: N = 7, Arr[ ] = { 3, 1, 4, 1, 5, 9, 2 }
Output: 4
Approach: The approach is based on binary search technique.
- Perform binary search over all possible numbers and check if the current number can be obtained as a median by choosing any number of elements from the array under the given condition.
- Out of all the possible values, the maximum one will be the answer.
- To check if the current value x can be a median or not, follow the simple observation that if there are more number of elements ≥ x in the subsequence then the median of the subsequence is at least x.
- After that declare a modified array from the original array such that:
- For each i (0 ≤ i ≤ N-1 ) if Arr[i] ≥ x, then modified[i]=1,
- Else modified[i] = -1.
- Now, if it is possible to find a subsequence in the modified array (following the given condition that at least one of the ith and (i+1)th elements must be chosen) such that:
- If the sum of all elements of the subsequence is positive, then current x can be obtained as a median.
- The sum of the subsequence being positive from the modified array signifies that there are more elements ≥ x, in the original array.
- Hence, x can be a possible median.
- To find if such a subsequence sum can be obtained from the modified array, it is sufficient to find the maximum possible subsequence sum(with the given condition) from the modified array and compare it with 0.
- If it is greater than 0, then-current x can be a median.
- To find the maximum subsequence sum, we will use dynamic programming as explained in the code.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int dp[100000 + 5][2]; // Function to find maximum subsequence sum // from the array under given condition // using dynamic programming int max_subsequence_sum( int arr[], int n, int i, int last) { // If we have taken last element already // then last = 1 else last = 0 if (i >= n) { return 0; } // Already calculated and stored in dp // ao return directly if (dp[i][last] != -1) { return dp[i][last]; } if (last == 1) { // Last element is taken already // so we can either take // the current element or leave it int t1 = arr[i] + max_subsequence_sum(arr, n, i + 1, 1); int t2 = max_subsequence_sum(arr, n, i + 1, 0); return dp[i][last] = max(t1, t2); } else { // Last element is not taken // Hence we need to take // the current element int t = arr[i] + max_subsequence_sum(arr, n, i + 1, 1); return dp[i][last] = t; } } // Helper function to reset // dp values for each call int helper_max_sub_sum( int arr[], int n) { memset (dp, -1, sizeof (dp)); int max_sub_sum = max_subsequence_sum(arr, n, 0, 1); return max_sub_sum; } // Function to check if the given median // Can be obtained by // Choosing any subsequence of the array // Under given constraints bool is_given_median_possible( int arr[], int n, int median) { int modified[n]; // Creating the modified array as explained for ( int i{ 0 }; i < n; i++) { if (arr[i] >= median) { modified[i] = 1; } else { modified[i] = -1; } } int max_sub_sum = helper_max_sub_sum(modified, n); // If max_sub_sum > 0 then current // median is possible if (max_sub_sum > 0) { return true ; } return false ; } // Function to binary search // Over all possible values of median // To find the max possible median int binary_search_for_median( int arr[], int n) { int ans = 1; int low = *min_element(arr, arr + n); int high = *max_element(arr, arr + n); while (low <= high) { int mid = low + (high - low) / 2; if (is_given_median_possible(arr, n, mid)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } // Driver code int main() { int N = 7; int Arr[] = { 3, 1, 4, 1, 5, 9, 2 }; // Storing the function in ans variable int ans = binary_search_for_median(Arr, N); cout << ans << endl; return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG { static int dp[][] = new int [ 100000 + 5 ][ 2 ]; // Function to find maximum subsequence sum // from the array under given condition // using dynamic programming static int max_subsequence_sum( int arr[], int n, int i, int last) { // If we have taken last element already // then last = 1 else last = 0 if (i >= n) { return 0 ; } // Already calculated and stored in dp // ao return directly if (dp[i][last] != - 1 ) { return dp[i][last]; } if (last == 1 ) { // Last element is taken already // so we can either take // the current element or leave it int t1 = arr[i] + max_subsequence_sum(arr, n, i + 1 , 1 ); int t2 = max_subsequence_sum(arr, n, i + 1 , 0 ); return dp[i][last] = Math.max(t1, t2); } else { // Last element is not taken // Hence we need to take // the current element int t = arr[i] + max_subsequence_sum(arr, n, i + 1 , 1 ); return dp[i][last] = t; } } // Helper function to reset // dp values for each call static int helper_max_sub_sum( int arr[], int n) { for ( int i= 0 ;i<dp.length;i++){ for ( int j= 0 ;j<dp[i].length;j++){ dp[i][j]= - 1 ; } } int max_sub_sum = max_subsequence_sum(arr, n, 0 , 1 ); return max_sub_sum; } // Function to check if the given median // Can be obtained by // Choosing any subsequence of the array // Under given constraints static boolean is_given_median_possible( int arr[], int n, int median) { int modified[] = new int [n]; // Creating the modified array as explained for ( int i = 0 ; i < n; i++) { if (arr[i] >= median) { modified[i] = 1 ; } else { modified[i] = - 1 ; } } int max_sub_sum = helper_max_sub_sum(modified, n); // If max_sub_sum > 0 then current // median is possible if (max_sub_sum > 0 ) { return true ; } return false ; } // Function to binary search // Over all possible values of median // To find the max possible median static int binary_search_for_median( int arr[], int n) { int ans = 1 ; int low = 99999999 ; int high = - 9999999 ; for ( int i= 0 ;i<arr.length;i++) { low = Math.min(low, arr[i]); high = Math.max(high, arr[i]); } while (low <= high) { int mid = low + (high - low) / 2 ; if (is_given_median_possible(arr, n, mid)== true ) { ans = mid; low = mid + 1 ; } else { high = mid - 1 ; } } return ans; } // Driver code public static void main (String[] args) { int N = 7 ; int Arr[] = { 3 , 1 , 4 , 1 , 5 , 9 , 2 }; // Storing the function in ans variable int ans = binary_search_for_median(Arr, N); System.out.println( ans); } } // This code is contributed by Potta Lokesh |
Python3
# Python code for the above approach # Function to find maximum subsequence sum # from the array under given condition # using dynamic programming def max_subsequence_sum(arr, n, i, last): if i > = n: return 0 if dp[i][last] ! = - 1 : return dp[i][last] if last = = 1 : t1 = arr[i] + max_subsequence_sum(arr, n, i + 1 , 1 ) t2 = max_subsequence_sum(arr, n, i + 1 , 0 ) dp[i][last] = max (t1, t2) return dp[i][last] else : t = arr[i] + max_subsequence_sum(arr, n, i + 1 , 1 ) dp[i][last] = t return dp[i][last] # Helper function to reset # dp values for each call def helper_max_sub_sum(arr, n): global dp dp = [[ - 1 for i in range ( 2 )] for i in range ( 100000 + 5 )] max_sub_sum = max_subsequence_sum(arr, n, 0 , 1 ) return max_sub_sum # Function to check if the given median # Can be obtained by # Choosing any subsequence of the array # Under given constraints def is_given_median_possible(arr, n, median): modified = [[ - 1 , 1 ][arr[i] > = median] for i in range (n)] max_sub_sum = helper_max_sub_sum(modified, n) return max_sub_sum > 0 # Function to binary search # Over all possible values of median # To find the max possible median def binary_search_for_median(arr, n): ans = 1 low = min (arr) high = max (arr) while (low < = high): mid = int (low + (high - low) / 2 ) if (is_given_median_possible(arr, n, mid)): ans = mid low = mid + 1 else : high = mid - 1 return ans # Driver Code N = 7 Arr = [ 3 , 1 , 4 , 1 , 5 , 9 , 2 ] ans = binary_search_for_median(Arr, N) print (ans) # This code is contributed by phalasi. |
C#
// C# code for the above approach using System; public class GFG{ static int [,] dp = new int [100000 + 5, 2]; // Function to find maximum subsequence sum // from the array under given condition // using dynamic programming static int max_subsequence_sum( int [] arr, int n, int i, int last) { // If we have taken last element already // then last = 1 else last = 0 if (i >= n) { return 0; } // Already calculated and stored in dp // ao return directly if (dp[i, last] != -1) { return dp[i, last]; } if (last == 1) { // Last element is taken already // so we can either take // the current element or leave it int t1 = arr[i] + max_subsequence_sum(arr, n, i + 1, 1); int t2 = max_subsequence_sum(arr, n, i + 1, 0); return dp[i, last] = Math.Max(t1, t2); } else { // Last element is not taken // Hence we need to take // the current element int t = arr[i] + max_subsequence_sum(arr, n, i + 1, 1); return dp[i, last] = t; } } // Helper function to reset // dp values for each call static int helper_max_sub_sum( int [] arr, int n) { for ( int i=0;i<dp.GetLength(0);i++){ for ( int j=0;j < dp.GetLength(1);j++){ dp[i, j]= -1; } } int max_sub_sum = max_subsequence_sum(arr, n, 0, 1); return max_sub_sum; } // Function to check if the given median // Can be obtained by // Choosing any subsequence of the array // Under given constraints static bool is_given_median_possible( int [] arr, int n, int median) { int [] modified = new int [n]; // Creating the modified array as explained for ( int i =0; i < n; i++) { if (arr[i] >= median) { modified[i] = 1; } else { modified[i] = -1; } } int max_sub_sum = helper_max_sub_sum(modified, n); // If max_sub_sum > 0 then current // median is possible if (max_sub_sum > 0) { return true ; } return false ; } // Function to binary search // Over all possible values of median // To find the max possible median static int binary_search_for_median( int [] arr, int n) { int ans = 1; int low = 99999999; int high = -9999999; for ( int i=0;i<arr.Length;i++) { low = Math.Min(low, arr[i]); high = Math.Max(high, arr[i]); } while (low <= high) { int mid = low + (high - low) / 2; if (is_given_median_possible(arr, n, mid)== true ) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } // Driver code static public void Main (){ int N = 7; int [] Arr = { 3, 1, 4, 1, 5, 9, 2 }; // Storing the function in ans variable int ans = binary_search_for_median(Arr, N); Console.Write( ans); } } // This code is contributed by hrithikgarg0388. |
Javascript
<script> // JavaScript code for the above approach: let dp = new Array(100000 + 5).fill(0).map(() => new Array(2).fill(0)); // Function to find maximum subsequence sum // from the array under given condition // using dynamic programming const max_subsequence_sum = (arr, n, i, last) => { // If we have taken last element already // then last = 1 else last = 0 if (i >= n) { return 0; } // Already calculated and stored in dp // ao return directly if (dp[i][last] != -1) { return dp[i][last]; } if (last == 1) { // Last element is taken already // so we can either take // the current element or leave it let t1 = arr[i] + max_subsequence_sum(arr, n, i + 1, 1); let t2 = max_subsequence_sum(arr, n, i + 1, 0); return dp[i][last] = Math.max(t1, t2); } else { // Last element is not taken // Hence we need to take // the current element let t = arr[i] + max_subsequence_sum(arr, n, i + 1, 1); return dp[i][last] = t; } } // Helper function to reset // dp values for each call const helper_max_sub_sum = (arr, n) => { for (let i = 0; i < dp.length; ++i) { for (let j = 0; j < dp[0].length; ++j) dp[i][j] = -1; } let max_sub_sum = max_subsequence_sum(arr, n, 0, 1); return max_sub_sum; } // Function to check if the given median // Can be obtained by // Choosing any subsequence of the array // Under given constraints const is_given_median_possible = (arr, n, median) => { let modified = new Array(n).fill(0); // Creating the modified array as explained for (let i = 0; i < n; i++) { if (arr[i] >= median) { modified[i] = 1; } else { modified[i] = -1; } } let max_sub_sum = helper_max_sub_sum(modified, n); // If max_sub_sum > 0 then current // median is possible if (max_sub_sum > 0) { return true ; } return false ; } // Function to binary search // Over all possible values of median // To find the max possible median const binary_search_for_median = (arr, n) => { let ans = 1; let low = Math.min(...arr); let high = Math.max(...arr); while (low <= high) { let mid = low + parseInt((high - low) / 2); if (is_given_median_possible(arr, n, mid)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } // Driver code let N = 7; let Arr = [3, 1, 4, 1, 5, 9, 2]; // Storing the function in ans variable let ans = binary_search_for_median(Arr, N); document.write(ans); // This code is contributed by rakeshsahni </script> |
Output
4
Time Complexity: O(N* log N)
Auxiliary Space: O(N)
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!