Last Updated on June 17, 2022 by Ria Pathak
Concepts Used
Sorting
Difficulty Level
Hard
Problem Statement (Simplified):
We have to find the maximum sum of elements from two arrays, such that you can select elements to add only from one array. You can switch array only at index where both indexes have the same elements.
Test Case
Input:
1
5 4
3 2 12 10 7
8 7 5 1
Output:
35
Explanation:
The maximum sum will be 1+5+7+10+12=35.See original problem statement here
Solving Approach :
1) We can sort both arrays here and maintain two sum values to keep the sum from both arrays.
2) As we can switch from one array to another only at indices containing the same elements, we can calculate sum up to the common element and save the larger one into our final sum.
3) We’ll calculate the sum of array elements in the respective sum variable until there comes an element that is common in both, we compare both sum variables and saves the maximum of both in our final sum. We repeat this until we get the end of arrays.
Final sum saved would be our answer.
Example
Let both arrays be,
Sorting both of them lets us count in a efficient way, so after sorting both arrays becomes,
We maintain 3 variables,
sumAfor sum from arrayA
sumBfor sum from arrayB
finalSumfor final sum to be printedNow, we traverse until a common element is found and add traversed elements in sum variables of respective array,
sumA=2 + 3 + 7=> 12
sumB=1 + 5 + 7=> 13We add the maximum sum value from both arrays in our
finalSumvariable, and setsumA,sumBto 0.
finalSum=finalSum+(sumA,sumB)
finalSum= 0 +max(12,13)
finalSum= 0 + 13
finalSum= 13Now, we repeat the same procedure until we encounter common elements or arrays are traversed completely,
sumA=10 + 12=> 22
sumB=8=> 8Hence, we save maximum of both in
finalSum,
finalSum=finalSum+(sumA,sumB)
finalSum= 13 +max(22,8)
finalSum= 13 + 22
finalSum= 35As, both arrays are traversed,
finalSumis our answer and we print it.
Solutions
#include <stdio.h>
void merge(int arr[], int start, int mid, int end){
int left[mid-start+1];
int right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int test;
scanf("%d",&test);
while(test--){
int m, n;
scanf("%d%d",&m,&n);
int a[m], b[n];
for(int i=0; i<m; i++)
scanf("%d",&a[i]);
mergeSort(a,0,m-1);
for(int i=0; i<n; i++)
scanf("%d",&b[i]);
mergeSort(b,0,n-1);
int i=0, j=0;
int finalSum=0,sumA=0, sumB=0;
while(i<m && j<n)
{
if (a[i]<b[j])
sumA += a[i++];
else if (a[i]>b[j])
sumB += b[j++];
else{
finalSum += (sumA>sumB)?sumA:sumB;
sumA = 0, sumB = 0;
while(i<m && j<n && a[i]==b[j]){
finalSum += a[i++];
j++;
}
}
}
while (i<m)
sumA+=a[i++];
while (j<n)
sumB+=b[j++];
finalSum+=(sumA>sumB)?sumA:sumB;
printf("%d\n",finalSum);
}
}
#include <bits/stdc++.h>
using namespace std;
void merge(int arr[], int start, int mid, int end){
int left[mid-start+1];
int right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int test;
cin>>test;
while(test--){
int m, n;
cin>>m>>n;
int a[m], b[n];
for(int i=0; i<m; i++)
cin>>a[i];
mergeSort(a,0,m-1);
for(int i=0; i<n; i++)
cin>>b[i];
mergeSort(b,0,n-1);
int i=0, j=0;
int finalSum=0,sumA=0, sumB=0;
while(i<m && j<n)
{
if (a[i]<b[j])
sumA += a[i++];
else if (a[i]>b[j])
sumB += b[j++];
else{
finalSum += max(sumA, sumB);
sumA = 0, sumB = 0;
while(i<m && j<n && a[i]==b[j]){
finalSum += a[i++];
j++;
}
}
}
while (i<m)
sumA+=a[i++];
while (j<n)
sumB+=b[j++];
finalSum+=max(sumA, sumB);
cout<<finalSum<<endl;
}
}
import java.util.*;
import java.io.*;
public class Main {
static void merge(int arr[], int start, int mid, int end){
int left[] = new int[mid-start+1];
int right[] = new int[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
static void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
while(test--!=0){
int m = sc.nextInt(), n = sc.nextInt();
int a[] = new int[m], b[] = new int[n];
for(int i=0; i<m; i++)
a[i] = sc.nextInt();
mergeSort(a,0,m-1);
for(int i=0; i<n; i++)
b[i] = sc.nextInt();
mergeSort(b,0,n-1);
int i=0, j=0;
int finalSum=0,sumA=0, sumB=0;
while(i<m && j<n)
{
if (a[i]<b[j])
sumA += a[i++];
else if (a[i]>b[j])
sumB += b[j++];
else{
finalSum += (sumA>sumB)?sumA:sumB;
sumA = 0;
sumB = 0;
while(i<m && j<n && a[i]==b[j]){
finalSum += a[i++];
j++;
}
}
}
while (i<m)
sumA+=a[i++];
while (j<n)
sumB+=b[j++];
finalSum+=(sumA>sumB)?sumA:sumB;
System.out.println(finalSum);
}
}
}
def merge(arr, start, mid, end): left = [0 for i in range(mid - start + 1)] right = [0 for i in range(end - mid)] for i in range(start, mid + 1): left[i - start] = arr[i] for i in range(mid + 1, end + 1): right[i - (mid + 1)] = arr[i] leftIndex = 0 rightIndex = 0 arrIndex = start while leftIndex <= mid - start and rightIndex < end - mid: if(left[leftIndex] < right[rightIndex]): arr[arrIndex] = left[leftIndex] leftIndex += 1 else: arr[arrIndex] = right[rightIndex] rightIndex += 1 arrIndex += 1 while(leftIndex <= mid - start): arr[arrIndex] = left[leftIndex] leftIndex += 1 arrIndex += 1 while(rightIndex < end - mid): arr[arrIndex] = right[rightIndex] rightIndex += 1 arrIndex += 1 def mergeSort(arr, start, end): if(end == start): return mergeSort(arr, start, (start + end) // 2) mergeSort(arr, ((start + end) // 2) + 1, end) merge(arr, start, (start + end) // 2, end) for _ in range(int(input())): m, n = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) mergeSort(a, 0, m - 1) mergeSort(b, 0, n - 1) i, j = 0, 0 finalSum, sumA, sumB = 0, 0, 0 while(i < m and j < n): if (a[i] < b[j]): sumA += a[i] i += 1 elif (a[i] > b[j]): sumB += b[j] j += 1 else: finalSum += max(sumA, sumB) sumA = 0 sumB = 0 while(i < m and j<n and a[i]==b[j]): finalSum += a[i] i += 1 j += 1 while (i<m): sumA += a[i] i += 1 while (j<n): sumB += b[j] j += 1 finalSum += max(sumA, sumB) print(finalSum)
[forminator_quiz id="1242"]
Space Complexity
O(
1)
This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.