Given two arrays x[] and y[] of N integers, the task is to form an array z[] of x[i] + y[j], (0 ?i, j < N) and find the max value of median of z[] formed by optimal rearrangement.
Examples:
Input: N = 5, x[] = {1, 2, 3, 5, 6}, y[] = {4, 7, 0, 9, 8}
Output: 12
Explanation: Let, z[] = { 1+0, 2+4, 5+7, 3+9, 6+8} = {1, 6, 12, 12, 14}
to get maximum Median i.e., 12.Input: N = 1, x[] = {11}, y[] = {12}
Output: 23
Approach: The problem can be solved based on the following idea:
The idea is to sort the array, and
- For first half (before the median positions) the new array must has the smallest possible elements to just discard this half of elements from both the arrays,
- Then from median positions onwards, traverse from right end of 1st array, and from median position of 2nd array, moving in opposite directions,
Find the minimum element formed by sum of these elements, that minimum element will be the median of the new array.
Follow the steps to solve this problem:
- If N =1, return x[0]+ y[0] as there is only single element,
- Otherwise, do the following steps
- First, sort both arrays and then divide the array from min to median-1 and median to max,
- Then, traverse from median to max and find the sum of opposite elements like, x[Median]+y[n-1], x[median+1]+y[n-2]…. up to Max.
- Out of these sums calculated above, the minimum one would be the median of the new array.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum median formed// by addition of two arraydouble findMedian(int* x, int* y, int n){ // If both arrays contains single element if (n == 1) { cout << x[0] + y[0] << endl; } else { // Sort both the arrays sort(x, x + n); sort(y, y + n); // Initialize counters int i = (n - 1) / 2; int j = n - 1; double Med = INT_MAX; // Find maximum median if (n & 1) { while (i < n) { Med = min(Med, (double)(x[i++] + y[j--])); } } else { vector<int> v; while (i < n) { v.push_back(x[i++] + y[j--]); } sort(v.begin(), v.end()); Med = (double)(v[0] + v[1]) / 2; } return Med; }}// Driver Codeint main(){ int x[] = { 1, 2, 3, 5, 6 }; int y[] = { 4, 7, 0, 9, 8 }; int N = 5; // Function call cout << findMedian(x, y, N) << endl; return 0;} |
Java
// JAVA program for above approachimport java.util.*;class GFG{// Function to find maximum median formed// by addition of two arraystatic void findMedian(int[] x, int[] y, int n){ // If both arrays contains single element if (n == 1) { System.out.print( x[0] + y[0]); } else { // Sort both the arrays Arrays.sort(x); Arrays.sort(y); // Initialize counters int i = (n - 1) / 2; int j = n - 1; int Med = Integer.MAX_VALUE; // Find maximum median if ((n & 1) != 0) { while (i < n) { Med = Math.min(Med, (x[i++] + y[j--])); } } else { ArrayList<Integer> v = new ArrayList<Integer>(n); while (i < n) { v.add(x[i++] + y[j--]); } Collections.sort(v); Med = ((v.get(0) + v.get(1)) / 2); } System.out.print( Med); }}// Driver Codepublic static void main(String[] args){ int x[] = { 1, 2, 3, 5, 6 }; int y[] = { 4, 7, 0, 9, 8 }; int N = 5; // Function call findMedian(x, y, N);}}// This code is contributed by code_hunt. |
Python3
# Python code to implement the above approach# Function to find maximum median formed# by addition of two arraydef findMedian(x, y, n): # If both arrays contains single element if (n == 1): return (x[0] + y[0]) else: # Sort both the arrays x.sort() y.sort() # Initialize counters i = (n - 1) // 2 j = n - 1 Med = 100000000000000000 # Find maximum median if (n % 2 == 1): while (i < n): Med = min(Med, (x[i] + y[j])) j -= 1 i += 1 else: v = [] while (i < n): v.append(x[i] + y[j]) i += 1 j -= 1 v.sort() Med = (v[0] + v[1]) // 2 return Med# Driver Codeif __name__ == "__main__": x = [1, 2, 3, 5, 6] y = [4, 7, 0, 9, 8] N = 5 # Function call print(" The maximum median formed by addition of two array is :" ,findMedian(x, y, N))# This code is contributed by Shushant Kumar |
C#
// C# program for above approachusing System;using System.Collections;using System.Collections.Generic;public class GFG { // Function to find maximum median formed // by addition of two array static void findMedian(int[] x, int[] y, int n) { // If both arrays contains single element if (n == 1) { Console.Write(x[0] + y[0]); } else { // Sort both the arrays Array.Sort(x); Array.Sort(y); // Initialize counters int i = (n - 1) / 2; int j = n - 1; int Med = Int32.MaxValue; // Find maximum median if ((n & 1) != 0) { while (i < n) { Med = Math.Min(Med, (x[i++] + y[j--])); } } else { ArrayList v = new ArrayList(n); while (i < n) { v.Add(x[i++] + y[j--]); } v.Sort(); Med = ((int)v[0] + (int)v[1]) / 2; } Console.Write(Med); } } static public void Main() { // Code int[] x = { 1, 2, 3, 5, 6 }; int[] y = { 4, 7, 0, 9, 8 }; int N = 5; // Function call findMedian(x, y, N); }}// This code is contributed by lokeshmvs21. |
Javascript
<script>// JavaScript code for the above approach // Function to find maximum median formed // by addition of two array function findMedian(x, y, n) { // If both arrays contains single element if (n == 1) { document.write(x[0] + y[0]); } else { // Sort both the arrays x.sort(); y.sort(); // Initialize counters let i = (n - 1) / 2; let j = n - 1; let Med = Number.MAX_VALUE; // Find maximum median if ((n & 1) != 0) { while (i < n) { Med = Math.min(Med, (x[i++] + y[j--])); } } else { v = []; while (i < n) { v.push(x[i++] + y[j--]); } v.sort(); Med = (v[0] + v[1]) / 2; } document.write(Med); } } // Driver Code // Code let x = [ 1, 2, 3, 5, 6 ]; let y = [ 4, 7, 0, 9, 8 ]; let N = 5; // Function call findMedian(x, y, N);// This code is contributed by sanjoy_62.</script> |
Output
12
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
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!
Share your thoughts in the comments
