Table of contents

Sum of the middle elements of two sorted arrays

Given two sorted arrays of the same size, find the sum of the middle elements after merging them. The merged array should also be sorted. If the total number of elements in the merged array is even, return the sum of the two middle elements.

Input/Output Examples

plaintext
Example 1:
Input:
arr1 = [1, 2, 4, 6]
arr2 = [3, 5, 7, 8]
Output: 11
Explanation: The merged array is [1, 2, 3, 4, 5, 6, 7, 8]. 
The middle elements are 4 and 5, and their sum is 9.

Example 2:
Input:
arr1 = [1, 12, 15, 26, 38]
arr2 = [2, 13, 17, 30, 45]
Output: 32
Explanation: The merged array is [1, 2, 12, 13, 15, 17, 26, 30, 38, 45]. 
The middle elements are 15 and 17, and their sum is 32.

Example 3:
Input:
arr1 = [2, 3, 6, 7]
arr2 = [1, 4, 5, 8]
Output: 10
Explanation: The merged array is [1, 2, 3, 4, 5, 6, 7, 8]. 
The middle elements are 4 and 5, and their sum is 9.

Approach to find the sum of middle elements of two sorted arrays

  1. Use Two Pointers to Merge Until Middle Elements:
    • Initialize two pointers, one for each array (i for arr1 and j for arr2).
    • Track the merged elements using a counter. Only merge until reaching the middle elements without fully merging the arrays.
  2. Find Middle Elements:
    • Since the arrays are of the same length, the total length of the merged array will be even. The two middle elements are at positions n - 1 and n (considering zero-based indexing on the merged array).
    • As you merge the elements from both arrays, keep track of these two middle elements without fully merging the arrays. 
  3. Calculate Sum of Middle Elements:
    • Once you reach the middle two elements (since the merged length is even), add them together and return the result as the sum.

C++ Program to find the sum of middle elements of two sorted arrays

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to find the sum of middle elements of two sorted arrays
int sumOfMiddleElements(vector<int>& arr1, vector<int>& arr2) {
    int n = arr1.size();
    int i = 0, j = 0, count = 0;
    int middle1 = -1, middle2 = -1;

    // Merge process until we reach the middle elements
    for (int count = 0; count <= n; count++) {
        if (i < n && (j >= n || arr1[i] < arr2[j])) {
            middle1 = middle2;
            middle2 = arr1[i];
            i++;
        } else {
            middle1 = middle2;
            middle2 = arr2[j];
            j++;
        }
    }

    return middle1 + middle2;
}

int main() {
    vector<int> arr1 = {1, 2, 4, 6};
    vector<int> arr2 = {3, 5, 7, 8};
    cout << "Sum of middle elements: " << sumOfMiddleElements(arr1, arr2) << endl;
    return 0;
}

Java Program to find the sum of middle elements of two sorted arrays

java
public class SumOfMiddleElements {

    // Function to find the sum of middle elements of two sorted arrays
    public static int sumOfMiddleElements(int[] arr1, int[] arr2) {
        int n = arr1.length;
        int i = 0, j = 0, count = 0;
        int middle1 = -1, middle2 = -1;

        // Merge process until we reach the middle elements
        for (count = 0; count <= n; count++) {
            if (i < n && (j >= n || arr1[i] < arr2[j])) {
                middle1 = middle2;
                middle2 = arr1[i];
                i++;
            } else {
                middle1 = middle2;
                middle2 = arr2[j];
                j++;
            }
        }

        return middle1 + middle2;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 4, 6};
        int[] arr2 = {3, 5, 7, 8};
        System.out.println("Sum of middle elements: " + sumOfMiddleElements(arr1, arr2));
    }
}

Python Program to find the sum of middle elements of two sorted arrays

python
# Function to find the sum of middle elements of two sorted arrays
def sum_of_middle_elements(arr1, arr2):
    n = len(arr1)
    i = j = 0
    middle1 = middle2 = -1

    # Merge process until we reach the middle elements
    for count in range(n + 1):
        if i < n and (j >= n or arr1[i] < arr2[j]):
            middle1 = middle2
            middle2 = arr1[i]
            i += 1
        else:
            middle1 = middle2
            middle2 = arr2[j]
            j += 1

    return middle1 + middle2

# Example usage
if __name__ == "__main__":
    arr1 = [1, 2, 4, 6]
    arr2 = [3, 5, 7, 8]
    print("Sum of middle elements:", sum_of_middle_elements(arr1, arr2))

Time Complexity

  • O(n): Since the algorithm only merges until the middle elements are reached, it takes linear time.

Space Complexity

  • O(1): The algorithm uses a constant amount of extra space for pointers and temporary variables.

DSA

Related Articles