Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Brute Force Approach 
2.1.
Algorithm 
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach 
3.1.
Algorithm 
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently asked questions
5.
Key takeaways
Last Updated: Mar 27, 2024

Sum of middle elements of two sorted arrays

Author Harsh Goyal
1 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

This blog will discuss the various approaches to solve the Sum of middle elements of two sorted arrays problem. Before jumping into the problem of getting the Sum of middle elements of two sorted arrays, let’s first understand a sorted array.

A sorted array is one of the combinations of the array in which all the elements of the array are either in non-increasing order or non-decreasing order.

Example:

Input: arr = [5, 4, 3, 10, 15, 25, 2, 100]

Sorted Array:- [2, 3, 4, 5, 10, 15, 25, 100]

In this Sum of middle elements of two sorted arrays problem, we need to return the sum of the array's middle elements after merging the two given sorted arrays. In this Sum of middle elements of two sorted arrays problem, our result will be the sum of two middle elements if the size of the resultant merged array is even, which means there will be two middle elements.

Note: The size of two sorted arrays is the same, i.e., ‘N’, which means the size of the resultant array will be ‘2N’.

Must Read, Array Implementation of Queue and Rabin Karp Algorithm

Brute Force Approach 

Brute Force Solution considers merging both the sorted arrays using merge sort. While comparing the elements of both the sorted arrays, we need to keep the track of the count, and when the count is equal to ‘N’ that will simply mean that we are in the center of the resultant array, and we need to take the sum of the elements at the index equal to count and one index which is before that count index. 

Algorithm 

Step 1. Create a function ‘getResult()’ that will accept 3 parameters, i.e., 2 sorted arrays naming ‘arr1’, ‘arr2’, and size of the sorted array ‘N’.

Step 2. Initialize two variables ‘x’, ‘y’ with zero, each one for each sorted array. 

Step 3. Declare three variables, ‘Count’:- to keep track of the index, ‘median1’ and ‘median2’:- to store the value of two middle elements.

Step 4. Make an iteration using the ‘count’ variable from 0 until its value is less than or equal to ‘N’. 

Step 5. Provide two edge cases, taking into account the value of ‘i’ and ‘j’, if they are equal to ‘N’, which means that they are the end of their respective sorted array, in this case, assign the value of ‘median2’ to ‘median1’ and initialize ‘median1’ with the first index of ‘arr2’. 

Step 6.  Similarly, if ‘j’ is equal to ‘N’, then assign the value of ‘median2’ to ‘median1’ and initialize ‘median1’ with the first index of ‘arr1’.

Step 7. Compare both the elements of the sorted array with ‘i’ and ‘j’ index and if ‘arr1[i]’ is less than or equal to ‘arr2[j]’ then store the previous median and increment the ‘i’ and if it is greater than ‘arr2[j]’ then increment the ‘j’. 

Step 8. Now, return the sum of ‘median1’ and ‘median2’. 
 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int getResult(int arr1[], int arr2[], int n) 
{
    int i = 0; 
    int j = 0;
    int count;
    int median1 = -1, median2 = -1;

    for (count = 0; count <= n; count++)
    {
        // Edge cases
        if (i == n)
        {
            median1 = median2;
            median2 = arr2[0];
            break;
        }
      
        else if (j == n)
        {
            median1 = median2;
            median2 = arr1[0];
            break;
        }
        if (arr1[i] <= arr2[j])
        {  
            /* Store the previous median */
            median1 = median2; 
            median2 = arr1[i];
            i++;
        }
        else
        {
            /* Store the previous median */
            median1 = median2; 
            median2 = arr2[j];
            j++;
        }
    }
      
    return (median1 + median2);
}
    
 int main() 
{
    int arr1[] = {5, 10, 78, 98, 100, 114};
      
    int arr2[] = {45, 70, 88, 94, 150, 164};
      
    int N = sizeof(arr1) / sizeof(arr1[0]);

    int res = getResult(arr1, arr2, N);
        
    cout << "Sum of middle element of two sorted arrays is :- " << res;
}

 

Output :

Sum of middle element of two sorted arrays is :- 182

Complexity Analysis

Time Complexity: O(N)

Incall to ‘getResult()’, we are traversing for ‘N’ times in the worst case, therefore, the overall time complexity is O(N).

Space Complexity: O(1)

As we are using constant space, therefore, the overall space complexity will be O(1).

Check out this array problem - Merge 2 Sorted Arrays

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach 

To optimize this sum of middle elements of two sorted arrays problem, we’ll try to find the middle elements of both the sorted arrays, and then we will compare them. 

Algorithm 

Step 1. In the function call ‘getResult()’, we need to calculate the median of both the sorted arrays and store it in ‘median1’ and ‘median2’. 

Step 2. We need to return twice of ‘median1’ or ‘median2’ if both are equal.

Step 3. And if they are not equal, and ‘median1’ is greater than ‘median2’, then it is pretty clear that median is present in either subarray of the first element of ‘arr1’ to ‘N / 2’ or it is present in a subarray of ‘median2’ to the end of ‘arr2’.

Step 4. And if they are not equal and ‘median2’ is greater than ‘median1’ , then median is present in either subarray of ‘median1’ to the end of ‘arr1’ or subarray of the first element of ‘arr2’ to ‘N / 2’.

Step 5. We need to repeat the above-stated process till the time size of both the subarrays becomes 2.

Step 6. Now we need to return the sum of max(arr1[0], arr2[0]) and min(arr1[1] , arr2[1]) if the size of 2 arrays is 2. 
 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
/* Function to get median of a sorted array */
int median(int arr[], int start)
{
  int n = start;
  if (n % 2 == 0)
    {
      return (arr[n / 2] + arr[n / 2 - 1]) / 2;
  }
  else
    {
      return arr[n / 2];
  }
}

int getResult(int a1[], int a2[], int n)
{
  // base case
  if (n <= 0)
  {
      return -1;
  }
  if (n == 1)
  {
      return (a1[0] + a2[0]);
  }
  if (n == 2)
  {
      return (max(a1[0], a2[0]) + min(a1[1], a2[1]));
  }

  //  Median of first array
  int m1 = median(a1, n);

  // Median of the second array
  int m2 = median(a2, n);

  // If medians are equal
  if (m1 == m2)
  {
      return m1;
  }

  // if m1 < m2 then
  if (m1 < m2)
  {
      if (n % 2 == 0)
      {
          return getResult(a1 + n/2 - 1, a2, n - n/2 +1);
      }
      return getResult(a1 + n/2, a2, n - n/2);
  }

  /* if m1 > m2 then median must exist in ar1[....m1] and
      ar2[m2...] */
  if (n % 2 == 0)
  {
      return getResult(a2 + n/2 - 1, a1, n - n/2 + 1);
  }
  return getResult(a2 + n/2, a1, n - n/2);
}

int main()
{

    int arr1[] = {5, 10, 78, 98, 100, 114};
    
    int arr2[] = {45, 70, 88, 94, 150, 164};
    
    int N = sizeof(arr1) / sizeof(arr1[0]);

    int res = getResult(arr1, arr2, N);
      
    cout << "Sum of middle element of two sorted arrays is :- " << res << endl;
}

 

Output:

Sum of middle element of two sorted arrays is :- 182

Complexity Analysis

Time Complexity: O(log N)

As we are using the Divide and Conquer algorithm over here, therefore, the overall time complexity is O(log N).

Space Complexity: O(1)

As we are using constant extra space, therefore, the overall space complexity is O(1).

Frequently asked questions

1) What is a median?

Median is referred to as the middle element of the array.

 

2) What is the effect of the size of the array on the median?

If the size of the array is even, then the value of median will be the average of the two middle elements, whereas if the size of the array is odd, then the value of median is the middle value itself.

 

3) What is the Divide and Conquer Algorithm?

It is the algorithm that is recognized to work by dividing the array and then working on it. For more knowledge on this algorithm, refer to this link.

Key takeaways

In this article, we discussed the What is Sum of middle elements of two sorted arrays problem, discussed the various approaches to solving this problem programmatically, and the time and space complexities. 

If you think that this blog helped you, then share it with your friends!. 

Refer to the DSA C++ course for more information.


Until then, All the best for your future endeavors, and Keep Coding.

 

Previous article
Missing Number in Array
Next article
Advantages and Disadvantages of Array
Live masterclass