Maximum possible pair sum at most K from two Arrays

View Discussion

Improve Article

Save Article

Like Article

Given two arrays arr1[] and arr2[] of sizes N and M and an integer K, the task is to find the maximum possible sum pair from two arrays such that the sum is at most K.

Note: You have to take one element from each array.

Examples: 

Input: arr1[] = {5, 4, 1, 2, 3}, arr2[] = {30, 20, 40, 10}, K = 30
Output: 25
Explanation: Maximum sum of a pair is (20 + 5) = 25 that is at most 30.

Input: toffee[] = {7, 6, 8}, candy[] = {9, 1, 5, 2, 8}, K = 5
Output: -1
Explanation: There is no such pair which have a pair sum less than or equal to 5

Approach: The basic idea to solve the problem is mentioned below:

Create all the possible pairs from arr1[] and arr2[]. From these pairs find a pair whose sum is the greatest and at most equal to K.

Follow the steps to solve the problem:

  • Define a variable (say sum = 0)to store the pair sum.
  • Traverse the array arr1[] from i = 0 to N:
    • For each element of arr1[] traverse from j = 0 to M of arr2[] to form all possible pairs and:
      • Calculate the pair sum of arr1[i] and arr2[j].
      • If the sum is greater than the maximum pair sum till now and not greater than K, update the maximum value.
  • After the loop ends, return the maximum value as the answer.

Below is the implementation of the above approach.

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int maximumAmount(int arr1[], int arr2[],

                  int k, int n, int m)

{

  

    

    

    

    int ans = INT_MIN, sum;

  

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

  

            

            

            sum = arr1[i] + arr2[j];

  

            

            

            

            if (sum > ans && sum <= k)

                ans = sum;

        }

    }

    return ans;

}

  

int main()

{

    int arr1[] = { 5, 4, 1, 2, 3 };

    int arr2[] = { 30, 20, 40, 10 };

  

    int N = sizeof(arr1) / sizeof(arr1[0]);

    int M = sizeof(arr2) / sizeof(arr2[0]);

  

    int K = 30;

  

    

    cout << maximumAmount(arr1, arr2, K, N, M);

  

    return 0;

}

Time Complexity: O(N*M)
Auxiliary Space: O(1)

By Julio MarchiPosted on