Maximum Sum Rupees

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 go through the best websites to learn coding to 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,

sumA for sum from array A

sumB for sum from array B

finalSum for final sum to be printed

Now, 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 => 13

We add the maximum sum value from both arrays in our finalSum variable, and set sumA, sumB to 0.

finalSum = finalSum + (sumA,sumB)

finalSum = 0 + max(12,13)

finalSum = 0 + 13

finalSum = 13

Now, we repeat the same procedure until we encounter common elements or arrays are traversed completely,

sumA = 10 + 12 => 22

sumB = 8 => 8

Hence, we save maximum of both in finalSum,

finalSum = finalSum + (sumA,sumB)

finalSum = 13 + max(22,8)

finalSum = 13 + 22

finalSum = 35

As, both arrays are traversed, finalSum is 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);
    }

  }
}

Space Complexity

O(1)

Previous post Maximum Divisors in a Range
Next post Longest Palindromic Substring

Leave a Reply

Your email address will not be published. Required fields are marked *